Gaden er opkaldt efter apostelen Sankt Paul, som har givet navn til Sankt Pauls Kirke.
Tidligere havde gadeforløbet flere forskellige navne: Salviegade, Enhjørningsgade og Pindsvinegade.
Desuden kaldtes en del af gaden H. P. Lorenzensgade efter en grosserer, der opførte husrækken. Lorentzen oprettede også en velgørende stiftelse i Rigensgade.
Mellem Sankt Pauls Plads og Borgergade ligger den ældste, bevarede række af husene i Nyboder (herover). De er opført omkring 1630. I et af husene ligger Nyboders Mindestuer.
Huset på hjørnet af Borgergade (længst til højre på billedet herover), er en officersbolig, der blev bygget omkring 1803 af Johan Boye Junge Magens (1748-1814).
Oprindeligt var gaden bebygget med de klassiske Nyboder-længer, men de blev revet ned i midten af 1800-tallet. I stedet blev der vest for Kronprinsessesgade opført boliger for Arbejdernes Byggeforening (billedet herover).
Arkitekten var Frederik Bøttger (1838-1920), der senere tegnede tilsvarende huse i bl.a. Kartoffelrækkerne og Humleby. Husene er i dag malet i forskellige farver.
Den del af gaden. der ligger tættest på Store Kongensgade fik i 1850’erne mere traditionelle etageejendomme, som bl.a. blev opført af grosserer H. P. Lorenzen.