У 1872 році на базі військового училища було відкрито учительську семінарію, де готували вчителів молодших класів.

Із документальних джерел та спогадів старожилів с. Миколаївка-Новоросійська Коростельових Святослава Сергійовича та Парасковії Іванівни, Куценко Марії Іларіонівни:

У 1872 році була відкрита учительська семінарія, в якій готували учителів молодших класів. Студенти займались революційною діяльністю, організовували гуртки. У листопаді 1905 року була, оголошена забастовка. Учні семінарії вимагали покращення викладання, розширення курсу природничих наук, збільшення розміру стипендії тощо. Частина вимог була задоволена, але через продовження революційної діяльності семінарія була закрита. На базі семінарії було відкрито вище початкове училище, в якому відкрили 4 класи початкової школи і чотири класи середньої школи.  Всього 8 років навчання. У 1913 році батько Коростельова С. С, Коростельов Сергій Пилипович був направлений на роботу у с. М-Новоросійську учителросійської мови (3-4 класи) та арифметики (2, 3, 4 класи). У неділю Сергій Пилипович займався з учнями позакласним читанням, знайомились із творами російських письменників. Крім цього,більшість учнів навчались грати на гітарі та балалайці. Сергій Пилипович організував великий оркестр учнів та вчителів. Навчання в  молодших класах було безкоштовним, а в 5-8- платне, але не дороге.

У 1918 році у зв’язку з переходом Бессарабії під владу Румунії, училище було перейменоване у гімназію. На  території села було іще дві початкових школи, де навчатись 4 роки окремо дівчата і окремо хлопці. Гімназія знаходилась по вулиці Комсомольській (сучасна назва), де зараз живуть Ярошенко К.К та Граматик О.С. Початкова школа для хлопчиків знаходилась у теперішньому комунгоспі, а дівчача початкова школа під час війни була зруйнована. Перед тим, як іти в початкову школу, діти один рік навчатись у дитячому садочку румунській мові. Навчання проводилось з 8.00 - до 12.00, а потім діти розходились по домах. Це було необхідно, тому що викладання деяких предметів велося румунською мовою.

Румуни проводили жорстку політику румунізації, але безуспішно, у 1934-1935 навчальному році перший клас гімназії набирався уже в Молдавії, тому що почався процес закриття гімназії, яка у 1937 році була зовсім закрита. У будинок гімназії перевели початкову школу.

З приходом радянської влади у 1940-1941 навчальному році була створена середня школа, в якій навчатись діти із сусідніх сіл: Успенівки, Кривої Балки, Ярославки. Під час війни1941-1945 років у с. М-Новоросійські працювала школа із 7 класів: 4 класи були обов’язковими, а в інші могли вступити за бажанням в Б-Дністровську гімназію теоретичну, в якій навчали різним дисциплінам, і гімназію індустріальну, яка надавала навики ведення сільського господарства.

Хто не вступав у гімназію, навчатись в М-Новоросійській школі у 5,6.7 класах. Теоретичному навчанню надавалось менше уваги, а практичному — більше.

         Після звільнення нашої території у 1944 році у будинку гімназії, аптеки, у всіх інших будинках, розташованих біля гімназії, відкрили середню школу. Через відсутність учнів 9-10 класів, відкритий був тільки 8 клас. У 1946-1947 навчальному році середня школа була переведена у районний центр, в Сарату. Багато учителів теж переїхали працювати в районний центр. Однак великими зусиллями секретаря   М-Новоросійської школи Владеско Марії Кирилівни, у селі знову були відкриті старші класи через рік. У школі працював великий учительський колектив:  Куценко Марія Іларіонівна, Костарчук Іван Никифорович, директор семилітки, Буш, Щербиник, Мамчур Олександр Григорович, директор середньої школи, Смагіна Любов Олексіївна - учитель - мовник, Смагін Георгій Михайлович - математик, Мамчур Лідія Захарівна - мовник, Климов Микола Матвійович – фізик, Естріна Сарра Іосипівна - географ, Толстолик Ніна Савівна - мовник. Бахметьєва Анастасія Василівна – мовник, Кулікова Ольга Федорівна - учитель англійської мови, Черній Марія Арсентіївна – учитель французької мови, Куликов Михайло Лаврентійович - математик, Толстой Андрій Володимирович – історик, Будов Микола Григорович - історик, Бєляєва Ніна Олександрівна - математик, Харковенко Ніна Микитівна - учитель початкових класів, Коростельов Сергій Пилипович - біолог - хімік, Муніца Михайло Іванович - учитель праці.

Школа працювала у дві зміни, у зв’язку з тим, що дітей було багато, а приміщення не дозволяло проводити навчання в одну зміну. У 1968 році у листопаді була відкрита нова двоповерхова школа, яка могла вмістити 480 учнів. Увесь педколектив, який працював у старому будинку школи, перейшов у нову школу, яка функціонує дотепер.