Nærmest Slagelsegade ses et karakteristisk knæk i gadeforløbet, der skyldes, at gaden fulgte de gamle ejerskel i området, og de afspejlede igen den befæstning, der i 1640'erne blev lagt fra Ny Vartov Skanse ved Trianglen frem til kysten og videre mod Kastellet. Knækket markerer en del af bastionen i denne voldlinje, der i øvrigt forsvandt allerede i 1661.
Den østlige del af Holsteinsgade ligger på en grund, hvor der i 1600-tallet lå kongelige fiskedamme med et intensivt karpeopdræt. Senere omdannedes arealet til lystanlæg og dammene til søer, som om vinteren blev brugt til skøjteløb. Haveanlæggene var i 1800-tallet vilde og romantiske med store piletræer, der spejledes i småsøerne. Efter 1890 blev søerne fyldt op og den nuværende bebyggelse opført.
I 1950'erne – hvor Østerbro indbyggermæssigt set var størst – lå der bl.a. De Forenede Tæppebankerier (i kælderen til nr. 3), trikotagehandleren ”Fynboen” (i nr. 7, stuen), en hattemager (i kælderen nr. 27), damefrisørsalonen ”New York” (i stuen nr. 27), ”Danmarks upolitiske radiolytterunion” (nr. 31), ”Strandvejs- og Øbroavisen” (samme sted) og ostehandleren Gouda (i 43, stuen).
I dag er Holsteinsgade én af de mere eksklusive gader i bydelen. Der er berlinerinspirerethistoricisme i arkitekturen. Alle bebyggelser i gaden har enten høj eller middel bevaringsværdi.
Nr. 9: Er en af de ældste bygninger i kvarteret, fra 1860'erne. Over indgangsdøren er en plade, som minder om udfaldet i Classens Have, hvor livjægerne i forbindelse med briternes belejring1807 trængte igennem netop på dette sted, hvor huset ligger i dag.[1][2] På hver sin side af pladen er der indmuret en kanonkugle.
