Idet flåden under Christian 4. voksede opstod der et behov for rigtige boliger til de menige og deres familier. Inden opførelsen af Nyboder, eksisterede der et lignende kvarter, nemlig “Skipperboderne”, der var blevet opført på Bremerholm og var forbeholdt officerer. Det var disse boliger, der dannede forbillede for det nye Nyboder, der opstod ikke langt fra det nuværende Østerport.
De første 20 huse af Nyboder blev opført i 1631 på de grunde, Christian 4. tidligere havde købt uden for København. Navnet på den nye bydel kaldtes først “dy Boer til Søefolckied” – senere “Bådsmandshusene”. Det blev til ca. 200 boliger på hver ca. 40 m² bestående af en stue på 19 m², et kammer, en forstue og et køkken fælles med nabolejligheden. Lejlighederne var spejlvendte to og to og vendte ryggen mod hinanden, hvilket gav problemer med varme og kulde, fordi nogle fik sol, andre ikke. Trods den beskedne størrelse ragede de op over datidens arbejderboliger.
1641 er det Nyboder ved at være færdig, som Christian 4. havde planlagt det i samarbejde med Hans van Steenwinckel den yngre og Leonhard Blasius – dvs. den del der ligger sydvest for Suensonsgade. Husenes farve var dengang nationale, dvs. hvide og røde – og ikke som i dag okkergule med rødt tag.
Nyboder anvendtes fortsat som lejeboliger for forsvarets personel – Holmens faste stok. Frem til 2006 har Søværnet haft fortrinsret til boligerne, men herefter har både Hæren og Flyvevåbnet fået brugsret til boliger og alle tre værn deler dem nu på lige vilkår. Hjemmeværnets personel har ikke brugsret til boligerne.
I dag omtales hele Nyboder-området som ét samlet område, men det er faktisk inddelt i De Grå Stokke, De Gule Stokke samt flere omkringliggende gader.
