Prigodom općeg popisa stanovništva, Komletinci se spominju kao mjesto u krajiškom području u kojem je potrebno otvoriti školu. Pretpostavlja se da je nakon toga i otvorena škola, ali, poput drugih graničarskih općina, općina se nije bila u stanju održavati pa je zatvorena.
Osnutak škole u Komletincima pokrenuo je prvi komletinački župnik, pop glagoljaš, don Luka Sučić, koji je za potrebe škole darovao polovicu zemljišta tadašnje župne potkućnice (danas je na tom mjestu kuća obitelji Topalović, nekadašnja stara škola). Osnutak škole pada na 31. prosinca 1830. godine. Školu je osnovalo pukovnijsko zapovjedništvo u Vinkovcima kao opću nižu pučku učionicu u trajanju od dvije godine s jednim odjelom i jednim učiteljem. Broj učenika i broj odjela se tijekom godina mijenjao. Tijekom godina mijenjale su se i dograđivale školske zgrade, školski se prostor proširivao i dopunjavao ustupanjem časničkih stanova za školu.
Općina je odmah sklopila ugovor s prvim učiteljem, vojnikom Antunom Gjojićem iz Komletinaca, uz godišnja beriva od 96 forinti. Drva kao deputat nije dobio jer je živio u svom selu. Ugovor je potvrdila Pukovnija 26.01.1831. godine. U školu je upisano 68 učenika. Iz sačuvane graničarske arhive vidi se da je školske godine 1855./56. bilo upisano 34 dječaka i 49 djevojčica. U prvi je razred bilo upisano 52 učenika, a u drugi 31 učenik. Opetovnicu je polazilo 15 dječaka i 31 djevojčica.
Prema pukovnijskom iskazu od 12. listopada 1882. ,što su ga potpisali pukovnik i školski nadzornik, školu je pohađalo 129 učenika, među kojima je bilo podjednako muške i ženske djece. Škola je više puta mijenjala lokaciju pa se tako našla i na otkupljenom zemljištu zadruge Mušić. Kako je ta školska zgrada bila neprimjerena za potrebe nastave, 1887. godine bivša krajiška vojarna i skladište (koja se nalazila na mjestu današnjeg dječjeg igrališta) pretvoreni su školu, a deset godina kasnije u neposrednoj blizini škole sazidana su dva učiteljska stana. Važno je istaknuti da je 10. rujna 1889. škola u Komletincima postala članom Hrvatskog pedagoško-književnog zbora.
Do kraja drugog svjetskog rata škola je radila kao četverorazredna osnovna škola s dva kombinirana odjeljenja. Pedesetih godina 20. stoljeća, znatno je porastao broj učenika u školi zbog naseljavanja stanovništva iz Dalmacije, Bosne i Hercegovine i Like. Tako je vrlo brzo broj učenika porastao na 367, što je bio veliki problem zbog ograničenog prostora pa se 1952. godine počinje graditi nova, današnja školska zgrada, u koju su učenici i učitelji uselili 1958. godine. Od školske godine 1957./1958. škola djeluje kao osmogodišnja škola. Zgrada je u potpunosti završena 1962. godine od kada djeluje pod današnjim nazivom: Osnovna škola ¨Vladimir Nazor¨, Komletinci.
