Pilsēta dibināta 1703. gadā, kad Aleksandrs MenšikovsPētera I uzdevumā šeit nodibināja ieroču rūpnīcu. Pēc Pētera I nāves rūpnīca panīka un 1734. gadā tika slēgta. 1773. gadā Katrīna Lielā šeit atkal nodibināja ieroču rūpnīcu. 1777. gadā apdzīvotajai vietai piešķīra pilsētas tiesības. Turpinājuma kara laikā no 1941. līdz 1944. gadam pilsētu bija ieņēmis Somijas karaspēks. 1977. gadā šeit tika novērots Petrozavodskas fenomens.
Etniski Petrozavdskas iedzīvotāji ir krievi (86,7 %) un karēļi (4,0 %).
Petrozavodska ir biatlonista Vladimira Dračova (Владимир Петрович Драчёв, 1966), futbolista Alekseja Kozlova (Алексей Анатольевич Козлов, 1986) un Baltkrievijas biatlonista Vadima Sašurina (Вадим Леонидович Сашурин, 1970) dzimtā pilsēta.