Krebs’ Skole er stiftet den 15. august 1872 af daværende inspektor ved Metropolitanskolen, overlærer C.P.J. Krebs.
I de første seks år af sin eksistens boede skolen forskellige steder. Den begyndte hjemme hos inspektor Krebs på 3. sal i Sortedamsgade (nu: Sortedams Dossering), og den flyttede siden først til Tordenskjoldsgade og dernæst til Nørregade 20. Men inspireret og bistået af en kreds af forældre byggede skolen i 1878 sit eget hus, huset i Stockholmsgade 5. Den 17. september 1878 drog skolen af sted fra Nørregade, væk fra byen, ud til Stockholmsgade, og tog det nye hus i besiddelse. I en lang årrække, helt frem til 1959, har dette hus i Stockholmsgade 5 været rammen om hele skolen, om samtlige dens klasser og alle dens discipliner. Den gamle skolebygning i Stockholmsgade 5 er stadig rammen om 1. til 5. klasses undervisning.
I takt med ændrede skolelove påbegyndtes allerede i løbet af 1950'erne en udvidelse af undervisningsaktiviteten. Fra det oprindelige 5-årige forløb til først et 7-årigt, så 9-årigt og endelig et 10-årigt forløb, og nye bygninger måtte anskaffes. Beboelsesejendommene Stockholmsgade 7 og 9 blev købt, og i takt med beboernes fraflytning blev ejendommen indrettet til skoleformål. Ligeledes blev der i 1960 opført et lavt pavillonbyggeri til klasse- og faglokaler, hvormed skolens nuværende bygningsmæssige udformning blev skabt.