Сплетом околности сигурни подаци о оснивању прве српске основне школе у Требињу нису сачувани. Многи наши угледни суграђани, цијењени лингвистичари и историчари (а нарочито Саво Пујић и Крсто Галић) бавили су се свестранијим и дубљим истраживањем, а њихови објављени радови упућују и на другу литературу. Сигурно је да је у јесен 1862. и почетком 1863. године у Требињу дјеловала Српска основна нарoдна школа и да је она са малим прекидима радила све до 1918. године.

Ово је била прва свјетовна основна школа у којој је настава извођена на матерњем, српском језику. Наша школа почела је радити 1884. године у згради црквене општине у улици Владимира Гаћиновића. Први учитељ био је Стево Делић, а уписано је 80 ученика од 1. до 4. разреда.

Након 1918. године новоформирана краљевина СХС, пеузима бивше зграде српских основних школа под кирију и у њима оснива државне основне школе. Школске 1951/52. школа прераста у осмољетку са уписаних 688 ученика. Први директор био је Вељко Ковачевић из Билеће.

Зна се да су почетком шездесетих година,1960., одлуком Народног одбора Среза требињског формиране двије основне школе: "Прва основна школа" и "Друга основна школа" које су радиле у неколико школских зграда. Наша школа радила је под називом "Прва основна школа" у двије зграде, обје у центру града, око градске пијаце - једна гдје је данас смјештен "ПИО", а друга у згради некадашњег ђачког дома у којој је прије другог свјетског рата била женска домаћинска школа ". Ова школска зграда рађена је 1894. године.Друга основна школа" радила је у згради у којој је сада Музеј Херцеговине у Старом граду.                                                                                                                                                                

У недостатку учионичког простора користили су, за одржавање наставе физичког васпитања, заједничку салу која је била смјештена у данашњем парохијском дому. Почетком осамдесетих одваја се један дио ученика у новоизграђене објекте у насељу Горица и Полице (Друга основна школа и Трећа основна школа), а наша школа пресељава из садашње зграде "ПИА" у простор у Старом граду.                                                                  

Први директор "Прве основне школе" био је Вељко Ракић. Слиједе Марко Крунић, Вукашин Перишић, Саво Мијановић, Неђељко Ножица, Драгослав Ђордан , Милорад Стевовић. Директор школе од 1.8.2013. године је Дарко Јегдић, професор разредне наставе.

1974. године долази до интеграције и формирања Центра основних школа и предшколских установа.   Школске 1983/84. године школа пресељава у данашњу школску зграду у насељу Брегови и даље под називом "Прва основна школа" који 17.05.1995. године мијења у назив Основна школа "Јова Јовановић-Змај".  

На сједници ШО ОШ "Јова Јовановић Змај" Требиње одржаној дана 28.02.2012. године одлучено је да школа промијени назив у ЈУ Основна школа "Јован Јовановић Змај" Требиње, као и да се нови назив користи од школске 2012/13. године. Влада РС Рјешењем бр. 04/1-012-2-1490/12 дала је сагласност на промјене назива.