Заснаваны ў 1663 годзе як вартавы пункт на паўднёва-ўсходняй ускраіне Рускай дзяржавы; падвяргаўся нападам крымскіх татараў і нагайцаў. У верасні 1670 года узяты атрадамі Сцяпана Разіна. З 1719 года цэнтр Пензенскай правінцыі ў складзе Казанскай губерні; у 1723 годзе заснаваны гарадавы магістрат (да 1866 года). У жніўні 1774 года праз Пензу прайшла армія Емяльяна Пугачова. Са снежня 1780 года цэнтр намесніцтва, ператворанага ў 1796 годзе ў губернскі горад. У 1797—1801 гадах павятовы горад Саратаўскай губерні, з 1801 года губернскі горад. У 1874 годзе праз Пензу прайшла Сызрана-Вяземская чыгунка, а ў 1895 годзе пабудавана чыгунка Пенза-Рузаеўка. У 1928—1930 гадах цэнтр Пензенскай акругі Сярэдне-Волжскага краю, з 4 лютага 1939 года — абласны цэнтр.