Кітапхана алғаш рет 1867 жылы Перовск қаласында (қазіргі Қызылорда) Ақмешіт уезінің әскери бекінісінің халқы үшін ашылды. Кітапхана Ресейдің қалаларынан революциялық қозғалысқа қатысқаны үшін патша үкіметінен жер аударылған озық прогрессивті ойлы адамдармен ұйымдастырылды. Кітапхана алдыңғы қатарлы зиялылар мен ауқатты қазақтардың қаржыларынан ұйымдастырылған. 1917 жылға дейін қалалық көпшілік кітапхана қызметін атқарған. 1938 жылы Қызылорда өз алдына бөлініп, облыс орталығы болғаннан кейін, облыстық кітапхана қайта құрылды. Оның алғашқы директоры болып Л.И.Дмитриева тағайындалды.1973 жылы кітапхана Ыбырай Жақаев көшесіндегі 930 шаршы метрлік мекен-жайға көшірілді. Оқырмандарға 70 орындық оқу залы ашылды.1983 жылы облыстық кітапхана болып қайта құрылып, жазушы Максим Горький есімі берілді. Уақыт өте еліміз егемендік алғаннан кейін 1999 жылы Қазақстан Республикасы Үкіметінің 21 сәуірдегі «Қазақстан Республикасының білім және мәдениет мекемелеріне есімдер беру және оларды қайта атау туралы» қаулысына байланысты облыстық әмбебап кітапханасына халық жазушысы, ақын Ә.Тәжібаевтың есімі берілді. 2000 жылы Ә.Тәжібаев атындағы ОӘҒК электронды басылымдар қоры қалыптаса бастады. Электронды оқу залы ашылды. Желтоқсан айынан бастап электронды оқу залы Интернет жүйесіне қосылды. 2003 жылы Республикалық автоматтандырылған кітапхана жүйесі (РАБИС) бағдарламасы бойынша жұмыс жүргізіле бастады. 2009 жылы қараша айында кітапхана типтік жобада салынған жаңа ғимаратқа көшірілді.

Қазіргі таңда кітапхана заманауи компьютерлік құрал-жабдықтармен жасақталған, тұтынушылардың жас ерекшеліктеріне қарамастан барлық санаттарына қызмет көрсететін өңірдегі ең ірі ақпараттық мәдени орынға айналып отыр. 

Ғимараттың жалпы алаңы 8413,5 шаршы метрді құрайды.

Кітапхана ғимараты негізгі 3 қабаттан, цокольді және техникалық қабаттардан тұрады. Цокольді қабатта кітап қорларын сақтау және қосалқы қызмет көрсету бөлмелері орналасқан.

Кітапханада оқырмандарға қызмет көрсететін 9 бөлім және 7 сектор жұмыс істейді.