Его призвали на службу 2 июня 1940 года, за год и 20 дней до начала Великой Отечественной войны, а вернулся домой Максим Михайлович почти семь лет спустя, 29 апреля 1947 года. Все эти годы он служил в приданных к Черноморскому флоту частях. Его военная специальность именовалась электрик-слаботочник. Это означает, что он обслуживал на кораблях радио и телефонные линии, аккумуляторные батареи. Хоть и была его часть приданной к флоту, но во время войны его не раз забирали на тот или иной корабль, который выполнял боевые задачи в море. Это случалось, когда штатный специалист личного состава корабля выбывал из строя, потом его снова возвращали в часть и снова при необходимости забирали на другой корабль уходящий на задание.

Семь лет службы прошли у Максима Михайловича в части, которая называлась Служба наблюдения и связи и базировалась по восточному побережью Черного моря: в Геленджике, Туапсе, Сухуми, Поти. Матросу приходилось быть то в службе наблюдения и связи, то охраны, а то и выходить на судах в море. Особо запомнился выход в море на пароходе «Пестель» 19 июня 1944 года. К тому времени с начала войны пароход «Пестель» вывез в тыл более 20 тысяч раненых и 12 тысяч эвакуируемых граждан. Это были рейсы из Батуми, Поти, Сочи в осажденную Одессу, в сражающийся Севастополь, в Керчь и Камыш-Бурун, Новороссийск, Туапсе под частыми бомбежками немецкой авиации. Всего за время войны «Пестель» совершил 186 боевых рейсов, во время которых на судно сбросили более 500 бомб.

В этот рейс команде сухогруза «Пестель» предстояло выполнить какую то секретную операцию. Никто из матросов и старшин не знал, зачем сухогруз вышел в сторону турецких берегов и что находилось в ящиках. Судно уже было близко к цели, когда всплыла немецкая подводная лодка и выпустила торпеды по нашему кораблю. Тогда почти четверть команды погибла. Максим Михайлович получил легкое ранение кисти рук.

И снова берег, и была наглость гитлеровских подводников, когда они всплывали чуть ли не рядом с берегом и в упор расстреливали наших моряков, но потом береговые части хорошо вооружили зенитками и пушками, и теперь уже советские воины били прямой наводкой по наглецам, выныривавшим из морской пучины.

Перед мобилизацией на флот Максим Михайлович Колотнеча работал уполномоченным по торговле на строительстве Чикского водохранилища и поэтому через две недели после возвращения со службы Максим Михайлович уже возглавлял торговый отдел Сергиевского потребительского общества. И почти до самого ухода на пенсию его трудовой путь был связан с потребительской кооперацией, в том числе последние 22 года – с Кореновским горпо, которым он успешно руководил.

Награжден медалью «За оборону Кавказа»

Звание: краснофлотец 
Место службы: р-н СНиС Потийской ВМБ ЧФ 
Медаль «За оборону Кавказа»