Som en del af kong Christians den 4.’s planer om en ny bydel, Ny-København, nord for det gamle København indenfor de oprindelige volde, blev der anlagt et helt kvarter med boliger for flådens ansatte.
De havde tidligere været indkvarteret i skipperboderne omkring Holmensgade ved flådeværftet Bremerholm.
Kongen mente, at det var bedst at flådens mandskab boede i nærheden af skibene og når de ikke var spredt over hele byen, kunne de hurtigt kaldes sammen.
Ideen med et særligt kvarter til flådens personel var også, at familierne kunne kunne hjælpe hinanden, når mændene ikke var hjemme.
Af praktiske hensyn fik de helt ensartede Nyboder-huse husnumre, hvad der i 1600-tallet endnu ikke brugtes andre steder i København. Nummereringen er fortløbende, så det traditionelle system med lige numre på højre side af gaden og ulige på venstre, ikke gælder her.
Kvarteret hed fra starten De nye bådsmandsboder, men det blev hurtigt til det mere mundrette: Nyboder.
Opførelsen begyndte i 1631.
Bebyggelsen bestod fra starten af 20 længer med 600 helt ensartede huse på omkring 40 kvadratmeter i én etage. De er senere forhøjet til to etager.
I 1750’erne blev der opført en række nye huse i to etager, som Phillip de Lange (1704-1766) tegnede. De lå nord for det oprindelige Nyboder og dannede gaderne Delfingade, Krokodillegade m.fl.
Senere i 1700-tallet kom flere huse til efter tegninger af G. D. Athon (1714-1781) og C. F. Harsdorff (1735-1799).
Frem mod 1700-tallets slutning, blev der tilføjet ca. 150 huse til den oprindelige plan. Der blev også bygget fem større officersboliger.
I midten af 1800-tallet flyttede Flådens aktiviteter helv væk fra Gammelholm og var nu udelukkende koncentreret på Nyholm.
Derfor solgte Staten ud af grundene i Nyboder. Flere længer blev revet ned, og i stedet opført boliger af Arbejdernes Byggeforening i tidens stil i Gernersgade, Krusemyntegade og Sankt Pauls Gade.
I slutningen af 1800-tallet blev der igen bygget nyt, men nu i en helt anden byggestil, som manglede den klassiske gule farve. Det var arkitekten Rasmus Rue (1863-1944) og Olaf Schimdth (1852-1922), der stod for de sidst opførte Nyboder-huse, der ligger i Haregade, Gernersgade, Rævegade, Sankt Pauls Gade og Olfert Fischers Gade
I dag er der kun én længe tilbage af de én-etages Nyboder-huse fra 1600-tallet med det oprindelige udseende, nemlig den, der ligger ud til Skt. Pauls Gade (mellem Borgergade og Skt. Pauls Plads).
Ved siden af, i den lille gade Gammelvagt, ligger Nyboders gamle vagtbygning. Herfra udgik hver dag vagtfolk, der bankede på dørene, for at få søfolkene til at stå op. Københavns politi havde ingen myndighed i kvarteret – det stod Flåden selv for.
Det var fra starten planen at opføre en stor, rundkirke, Sankt Annæ Rotunda Kirke, som Nyboders kirke, men den blev aldrig bygget færdig. Langt senere blev Sankt Pauls Kirke i stedet bydelens sognekirke.
Selv om Nyboder var anlagt som en slags mønsterby for offentlige midler, var det ikke noget luksuriøst kvarter. Det varede mange år inden der blev lagt vand ind, og dagrenovationen måtte beboerne i starten selv sørge for. Vejene var ikke brolagte og derfor umulige at køre på, når det havde regnet.
Børnene i Nyboder begyndte allerede at arbejde som 7-8-årige. De blev ”rugdrenge”, fordi de ikke fik løn, men en portion rug til familien. Senere blev de ”kostdrenge”, og kom så endelige i lære. Naturalierne blev udleveret fra provianthuset på Slotsholmen.
I 1784 var der i Nyboder lidt over 1800 lejligheder med 5216 beboere. Efter nederlaget i 1807 var flåden reduceret og der var ikke behov for så mange boliger til personellet. I slutningen af 1800-tallet blev en del af boligerne ombygget.
Ved en lille plads mellem Krokodillegade og Øster Voldgade i den nordlige ende af Nyboder står en statue af bydelens grundlægger, kong Christian den 4.
Statuen er udført af billedhuggeren Vilhelm Bissen (1836-1913) og opstillet i 1900.