Библиотека была основана в 1939 году и располагась в двухэтажном кирпичном здании по ул. Советской (в настоящее время – гостиница «Турист»). На первом этаже находился отдел абонементов, читальный зал – на втором этаже.
В годы Великой Отечественной войны, кроме обслуживания читателей в библиотеке, библиотекари работали в госпитале для раненых в центре города. Здесь устраивались читательские конференции, обзоры, беседы для раненых (среди них были москвичи, ленинградцы, харьковчане).
В 1951 году библиотеку возглавила Свистунова Мария Давыдовна. В это время книжный фонд библиотеки составлял 10 тысяч экземпляров книг. Пополнение осуществлялось не только из государственных источников, но и с помощью читателей города, которые приносили книги в дар.
В годы освоения целины значительно увеличился приток населения. Молодежь с удовольствием шла в библиотеку, что повлекло за собой нехватку литературы. Фонд пополнялся украинской, белорусской литературой, много книг поступало из других библиотек со всего Союза.
В 1954 году Кустанайская городская библиотека насчитывала более тысячи читателей: учащиеся школ, рабочие, служащие, домохозяйки. В этом же году библиотека создает читательский актив, который помогает библиотечным работникам проводить всевозможные мероприятия. Зачастую сами библиотекари устраивали подворные обходы, где они рассказывали населению о библиотеке и интересной литературе.
В 1957 году городская библиотека оказывает большую помощь в оборудовании и снабжении литературой агитационных пунктов. Работало несколько библиотек-передвижек. Библиотека поддерживала связи и с домашними библиотеками, проводили совместные заседания.
30 сентября 1964 года (с этого года упоминается в материалах архива) городской библиотеке было присвоено имя советского писателя Николая Алексеевича Островского.
15 ноября 1967 года городская библиотека получила новое помещение, нижний этаж кооперативного дома по ул. Гоголя 80, площадь которого составляет 485,7 кв.м. Это создало лучшие условия для обслуживания жителей и увеличения книговыдачи.
В 1972 году произошла централизация городских библиотек. Первым директором Централизованной библиотечной системы была Гайнуллина Римма Темирбаевна, Заслуженный работник культуры Казахской ССР.