Zgrada Škole je sagrađena 1912. godine zahvaljujući fondaciji «Asilo per ragazzi poveri della citta di Pola Matteo Coceich», prvotno dom za siromašnu djecu i djecu bez roditeljske skrbi.
Odmah pri završetku Drugog svjetskog rata, u svibnju 1945. godine, nužno je bilo otvoriti jedan dom u koji bi se mogla smjestiti ona djeca, čiji su roditelji poginuli u ratu, kao i ona djeca kojoj je hitno bio potreban smještaj u domu. Zgrada za dom pronađena je u mjestu Lovranu. Za oko tristotinjak djece trebalo je omogućiti redoviti polazak u školu i tako je tadašnja vlast donijela odluku o otvaranju prvog razreda osnovne škole. U svibnju 1946. cijeli dom i škola pri domu iz Lovrana seli u Savudriju te je dom preimenovan u Dječji dom „Ruža Petrović“. Već u listopadu 1946. godine dom je preseljen iz Savudrije u Opatiju.
Početkom 1948. godine Dječji dom „Ruža Petrović“ iz Opatije seli u Pulu. Dolaskom u Pulu dolazi do spajanja osnovne škole pri Dječjem domu „Ruža Petrović“ s osnovnom školom „Veruda“ u Puli. Dječji dom bio je smješten u današnjoj zgradi naše škole (Brijunska 5), a osnovna škola djelovala je u ulici Pino Budicin 9.
U ožujku 1954. godine republički Savjet za prosvjetu i kulturu Narodne Republike Hrvatske dao je suglasnost za otvaranje osmogodišnje škole. Tadašnja četverogodišnja osnovna škola „Veruda“, postala je Osmogodišnja škola „Veruda“ te je preimenovana u: „II. narodna osmogodišnja škola – Pula“.
U rujnu 1954. godine „II. narodna osmogodišnja škola – Pula“ preseljena je u zgradu Dječjeg doma „Ruža Petrović“, u tadašnju ulicu Svetozara Markovića 3, to je ujedno sadašnja naša zgrada na adresi Brijunska 5.
U lipnju 1958. godine Školski odbor odlučio je školi dati naziv „Vladimir Gortan“, da bi na Dan škole, u lipnju 1961. godine, došlo do svečanog i službenog proglašenja imena škole u: Osnovna škola „Vladimir Gortan“ u Puli.
Velika adaptacija stare, ruševne zgrade OŠ Vladimir Gortan dogodila se za vrijeme ljetnih praznika 1986. godine. Škola je tada dobila svoje novo ruho. Nova školska godina je kasnila desetak dana za niše razrede, a radovi su se obavljali od temelja do krova i stajali su 320 milijuna ondašnjih dinara. Viši razredi nastavu su morali pohađati u OŠ Bratstvo i jedinstvo (današnja OŠ Veruda) u poslijepodnevnoj smjeni. Škola je otvorena 21. studenoga 1986. godine, a tadašnji ravnatelj škole Roberto Mišković zahvalio je svima koji su pružili pomoć da bi došlo do obnavljanja zgrade, koja takav izgled ima i danas. Međutim, učenici OŠ Vladimir Gortan još uvijek su bili bez sportske dvorane…
Od rujna 1992. godine, odnosno od školske godine 1992./1993. naša škola je preimenovana u Osnovna škola Stoja, naziv prema gradskoj četvrti kojeg nosi i danas.
Ostvarenje davno željenog sna, izgradnje sportske dvorane, započelo je u prosincu 2005. godine kada je položen kamen temeljac, a izgradnja je koštala 12 milijuna kuna. Dvorana je završena s početkom školske godine 2008./2009., točnije svečano je otvorena u listopadu 2008. godine.