Pilsētas nosaukums cēlies no mokšu valodas un nozīmē ‘Purvainās upes beigas’. Pilsēta dibināta 1663. gadā pēc cara Alekseja I rīkojuma kā cietoksnis Krievijas dienvidaustrumu nomalē. 1708. gadā kļuva par Kazaņas guberņas apriņķa centru, bet 1719. gadā par Penzas provinces centru. 1796. gadā nodibināta Penzas guberņa, bet jau nākošajā gadā tā likvidēta un Penza kļuva par apriņķa centru Saratovas guberņā. 1801. gadā Penzas guberņa tika izveidota no jauna un Penza bija tās centrs līdz 1928. gadam. 1874. gadā atklāta dzelzceļa satiksme līnijā Moršanska—Sizraņa. No 1928. līdz Penzas apgabala izveidošanai 1939. gadā Penza bija rajona centrs dažādos apgabalos un novados.
Otrā pasaules kara laikā uz Penzu evakuēti daudzi uzņēmumi no PSRS rietumu daļas un pilsēta strauji kļuva par nozīmīgu rūpniecības centru.