15 октября 1833 года в Петрозаводске по прямому указанию Министерства внутренних дел олонецкому губернатору А. И. Яковлеву была открыта Публичная библиотека. Библиотекарем и книжным хранителем был назначен архивариус Казённой палаты Лаврентий Мартынович Никифоров.
Библиотека располагалась в освобождённых комнатах казённой губернаторской квартиры. Наибольшая часть библиотеки состояла из научно-популярной литературы и книг по сельскому хозяйству, естественным наукам и медицине. Для организации работы был создан Попечительский комитет, в состав которого вошли губернский предводитель дворянства, директор Олонецких горных заводов, вице-губернатор и губернский директор училищ. Деятельность публичной библиотеки прекратилась в 1850-х годах.
2 января 1860 года Публичная библиотека была возрождена. Библиотека открылась в залах Благородного собрания на Круглой площади. Один из организаторов — Павел Николаевич Рыбников.
Посещение библиотеки стало платным, стоимость библиотечного абонемента была обусловлена количеством одновременно получаемой литературы.
После отъезда Рыбникова во второй половине 1860-х годов библиотека снова прекратила существование.
В июне 1870 года во время посещения Петрозаводска Великим князем Алексеем Александровичем была открыта подписка на возрождение Публичной библиотеки. Было собрано 200 рублей, узнав о проведённой акции, Великий князь назначил от себя в пользу библиотеки 300 рублей. В результате библиотека была открыта и названа Алексеевской.
Располагалась она в здании бывшей городской гауптвахты. Через несколько лет спустя положение библиотеки стало ухудшаться: поступало всё меньше средств, начались проблемы с содержанием помещения.
С 1918 года библиотека возобновила свою работу, однако во время пожара в 1918 году она почти полностью сгорела.
В 1919 году была создана Губернская библиотека-читальня, куда вошли фонды библиотек духовной и учительской семинарий, мужской и женской гимназий и коммерческого клуба. В 1920-е годы заведовали библиотекой Никольский И. М. (1886-1935)[3], в прошлом земский учитель[4], Бойцов Павел Алекандрович, Надежин Алексей Алексанлрович, в 1933—1937 гг. Молодьков Семён Федотович.
С 1922 года библиотека получает новое название — Карельская областная библиотека, а с 1925 года — Карельская публичная библиотека.
В 1941 году в связи с начавшейся оккупацией Карелии часть фондов библиотеки была эвакуирована в город Кемь. Около 10 тысяч экземпляров изданий хранились на станции Вонгуда Кировской железной дороги (Архангельская область). Часть фонда была уничтожена во время оккупации Петрозаводска финскими войсками (1941—1944), часть вывезена в Финляндию (В 1945 году были возвращены из Финляндии 14 вагонов книг библиотеки). В Кеми библиотека возобновила работу в 1944 году.
В 1947 году библиотека открыта в Петрозаводске в бывшем Дворце Труда на проспекте Карла Маркса. Библиотека получила новое название — Государственная Публичная библиотека Карело-Финской ССР.
В 1959 году библиотека переехала в новое здание, построенное по проекту петрозаводского архитектора К. Я. ГутинА на улице Пушкинской. Здание является памятником культуры республиканского значения.
В 1960 году библиотека награждена Почётной грамотой Президиума Верховного Совета РСФСР.
В 1991 году библиотека получила статус Национальной библиотеки Республики Карелия.
В 2009—2016 годах была проведена реконструкция здания библиотеки и строительство пристройки.
