Nylund skole ligger i Storhaug bydel. Skolen skal være reist av en million steiner - så er det sagt i alle fall. Nylund skole ble bygd i årene 1915-1917 etter tegninger som opprinnelig var laget for en skole på Østlandet, der snømengdene er større enn her. Skolen har derfor fått et svært skrånende tak.
I 1917 sto Nylund skole ferdig, en ruvende grå murbygning som viste godt igjen i omgivelsen og som var synlig på lang avstand. Kjelleretasjen lå høyt over jorden, deretter kom tre fulle etasjer og til slutt tre loftsetasjer under det høye skråtaket. Da den var ny, ble den i Stavanger Aftenblad omtalt som høyreist og staselig, som en pryd for byen og med vakker arkitektur. Det var Stavanger Cementvarefabriks arkitekt-kontor som hadde utarbeidet tegningene, og byggingen pågikk i rundt 1 1/2 år. I trappeoppgangene og utvendig var det ornament av porfyr som var utført av stukkatør Jensen.
Den første skolestyreren var Abraham Tønnessen. Ved åpningen var det 954 elever fordelt på 30 skoleklasser. Allerede neste år var det 51 klasser med 1606 elever, og i 1920 var der 54 klasser med 1681 elever. Disse tall illustrerer den store befolkningsvekst som fant sted i dette strøket på den tid. De forklarer også hvorfor det var nødvendig å gi skolen så svære dimensjoner. Den nye skolen fikk navnet Nylund, etter det strøket hvor den ble reist. Dette var en parsell av Hetlandsmarken som bare besto av myr og utmark, og som i 1860 ble kjøpt av kjøpmann og skipsreder Berge Bergesen. Bergesen ryddet og dyrket opp parsellen, plantet en god del trær og kalte stedet for Nylund.
Skolens adresse er Nylundsgata 1. Ellers er den omgitt av tre andre gater, hvorav to er oppkalt etter fremragende pedagoger. Mot vest grenser skolen til Bolette Wieses gate oppkalt etter Bolette Wiese som i 1856 startet en pikeskole i Stavanger. Mot sør grenser skolen til Asbjørn Klosters gate. Han var en fremragende språklærer og en dyktig oppdrager og pedagog. Gaten øst for skolen er oppkalt etter skipsreder Michael Berentsen, som i sin tid eide eiendommen Østre Storhaug.
International School of Stavanger holdt til på Nylund skole i perioden 1972-1982. Også Steinerskolen holdt til her i en periode. I 2004/2005 ble det foretatt en omfattende rehabilitering av skolen. 55 millioner kroner ble brukt til en fullstendig rehabilitering, som blant annet omfatter nytt ventilasjonsanlegg, sanitæranlegg, dataanlegg, og utsmykning. I tillegg er det bygget nytt musikkrom, aula og gymnastikksal. Skolens fasade har også gjennomgått endringer i form av et moderne tilbygg i glass, med bro fra hovedbygget til gymsalen. I perioden fra og med høsten 2017 til og med høsten 2020, er det blitt skiftet vinduer i begge bygg, og et nytt uværsskur er på plass med egen klatrevegg.