Prema navodima učitelja Maksima Zlokovića, koji je radio u ovoj školi, škola u Bijeloj je počela s radom daleke 1812. godine. Škola je radila pri crkvi Sv. Bogorodice u Vali. Pohađala su je samo muška djeca, a izdržavana je od priloga roditelja i crkve. Škola je dala poznate pomorske kapetane, kao što su: Anto Želalić, Bogdan Zloković, Joko Đinović, Simo Zloković, Niko Šerović i mnogi drugi. Nastavu su izvodila uglavnom sveštena lica: Lazar Ercegović, Nikola Miajlović, Stefan Perazić, Ignjo Zloković.

1873. godine školu preuzima na izdržavanje Zemaljska vlada i ona postaje državna ustanova. Škola je i dalje u crkvenoj kući Ćeliji, međutim broj učenika se povećava i sazrijevaju uslovi za podizanje nove školske zgrade. Mještani su davali dobrovoljne priloge, a najviše je pomogao Jovo Vuković, koji je dao plac i staru zgradu. U vremenu dok se zgrada radila, ne čekajući njeno dovršenje, škola je iz Ćelije, 1875. godine premještena i radila je u staroj kući Zlokovića, na Pijavici.

1877. godine školska zgrada je završena i u njoj škola neprestano radi do 1955. godine. U školi postoje dva odjeljenja, a nastavu izvodi učitelj Ignjatije Zloković. Školske 1878/79. godine, učitelj Stanislav Margetić počinje, po nalogu školskih vlasti, da vodi „Školsku kroniku“, tj. Ljetopis škole.

1895. godine škola postaje mješovita – tako da je od tog perioda pohađaju i ženska djeca. Škola je brojala 91 učenika. Uvodi se u nastavu ženski ručni rad. U vrijeme Prvog svjetskog rata škola je radila s prekidima. Tada su nastavu izvodili učitelj i učiteljica, a na kraju svake školske godine, školski nadzornik za cijelu Boku, tada Kotoranin Andrija Lazarević, obilazio bi školu i ispitivao djecu.

Školske 1919/20. godine škola dobija novi naziv – Dvorazredna narodna osnovna škola. Nešto kasnije, naziv je promijenjen u – Državna osnovna škola. Od školske 1928/29. godine nastava se izvodi sa šest razreda u tri odjeljenja, sve do Drugog svjetskog rata. U toku rata škola radi s prekidima, s tim što i nastavu izvode Italijani, a službeni jezik je italijanski. Poslije oslobođenja, 1944. godine, škola je četverorazredna.

Od školske 1955/56. godine škola je podignuta na viši nivo – otvoreni su V i VI razred, škola je preseljena u drugu zgradu, zvanu „Palac“ (Zadužbina Milivoja-Mila i Ane Zloković), koja je adaptirana i kasnije zbog povećanja broja učenika, uz tu zgradu je fazno dograđen sadašnji objekat škole.

U tadašnjoj zgradi je bilo pet učionica i dva stana. Školu su pohađali učenici iz Bijele, Kamenara i Đenovića, ukupno 159 učenika u šest razreda. Školske 1956/57. godine otvoren je VII razred, dok je VIII razred otvoren sljedeće školske 1957/58. godine.

Odlukom NOO Herceg-Novi, 1. septembra 1962. godine, promijenjen je naziv škole u Matična osnovna škola Bijela. Istom odlukom, samostalne četvororazredne škole u Đenovićima, Baošićima, Bjelskim Kruševicama i Kamenarima, postale su područna odjeljenja ove škole.

Sadašnje ime Osnovna škola „Orjenski bataljon“ škola dobija školske 1965/66. godine, a za Dan škole je proglašen 9. novembar. Tokom 1974. godine pokrenut je i čuveni Festival pionirskog proznog stvaralaštva, ugostivši pisce poput Branka Ćopića i Desanke Maksimović. Škola je dobitnik „Oktobarske nagrade“ Herceg-Novog za 1979. godinu i „Majske nagrade“ za 1985. godinu.

Od 1. septembra 2004. godine Osnovna škola „Orjenski bataljon“ ima status devetogodišnje osnovne škole i u njoj se realizuje program reforme osnovnog obrazovanja i vaspitanja u Crnoj Gori.