"Norssi" on Oulun vanhan koulun jälkeläinen. Vanhimmat edeltäjät olivat Oulun pedagogio 1609-1682, Oulun triviaalikoulu sekä apologistiluokka 1682-1842 sekä Yläalkeiskoulu (Hörge elementarskolan) 1842-1863, joka oli neljäluokkainen.
Koulu laajennettiin 1863 yliopistoon johtavaksi Oulun alkeisoppilaitokseksi (Elementarläsoverket i Uleåborg), jossa aluksi oli osittain suomi opetuskielenä ja josta ensimmäiset ylioppilaat valmistuivat 1866. Ruotsi määrättiin 1873 ainoaksi opetuskieleksi ja koulu toimi Oulun ruotsalaisena lyseona (Svenska lyceet i Uleåborg) 1874-1899. Koulu joutui siirtymään 1828 Pokkitörmälle rakennetusta talosta entiseen Svendelinin taloon 1890. Koulu toimi 1899-1904 Ruotsalaisena reaalilyseona, mutta määrättiin muuttumaan asteittain Suomalaiseksi reaalilyseoksi koska siinä oli vain 74 oppilasta.
Parina vuotena koulun nimenä oli Oulun toinen suomalainen lyseo, kunnes sortoajan senaatti 1915 mahtikäskyllään supisti sen Oulun suomalaiseksi keskikouluksi. Sen yhteydessä toimi muutamia vuosia (1919-1922) Oulun maanviljelys- ja teollisuus-jaostoinen lyseo. Oulun keskikoulu muutettiin 1955 Merikosken yhteislyseoksi, joka sai 1958 uuden koulutalon. Koulu lakkautettiin 1960 ja perustettiin Oulun normaalilyseo, joka lakkautettiin 1974, koska opettajankoulutus siirtyi yliopiston yhteyteen. Oulun yliopiston opettajan-koulutuslaitoksen harjoittelukoulun nimeksi tuli Oulun normaalikoulu. Samalla lopetti toimintansa 1961 perustettu Oulun opettajanvalmistuslaitoksen harjoituskoulu, joka liitettiin Oulun normaalikouluun ala-asteeksi. Arkkitehti Heikki Taskisen suunnittelemat uudet koulurakennukset valmistuivat 1982 ja 1983 yliopistoalueelle Linnanmaalle.