Именно так в июне 1933 года Михаил Грешилов стал курсантом Военно-морского училища имени Фрунзе в Ленинграде. После сдачи вступительных экзаменов его определили в штурманский дивизион сектора училища, готовившего командиров для подводного флота. Учеба давалась ему легко. Как он сам вспоминал в мемуарах, ему в практическом плане очень помог опыт работы электрика, а усидчивости и смекалки ему было не занимать. Летом 1937 года он выпустился из училища с лейтенантскими нашивками, женился и отправился служить по распределению на Черноморский флот. Его первой подводной лодкой стала «щука» Щ-202. «Щуки» относились к подводным лодкам среднего типа, составлявшим в то время основу советского подводного флота. Эти почти что 600-тонные корабли имели длину 59 метров, скорости 12,3 и 8,5 узла над и под водой соответственно, шесть торпедных аппаратов, четыре запасные торпеды и две 45-мм пушки. Экипаж по штату составлял 40 человек, из них семь относились к начальствующему составу. Одним из них был штурман, который помимо непосредственных и весьма ответственных обязанностей являлся еще и командиром боевой части, куда входили рулевые, штурманские электрики, связисты и акустики. Времени у молодого лейтенанта на раскачку не было – пришлось за считаные недели врастать в круг весьма многочисленных ежедневных обязанностей. Позднее Михаил Васильевич вспоминал:
Прекрасная школа, преподанная талантливому ученику, не пропала даром. Командование заметило способного молодого штурмана, и уже в январе 1939 года наш герой получил назначение на должность помощника командира подлодки А-1 того же флота. И здесь ему предстояло пройти серьезную школу, но уже опираясь не на положительный, а на отрицательный пример. Командиром этой субмарины являлся сравнительно немолодой человек, призванный на службу из кадров торгового флота, который так и не сумел стать военным моряком. Вся организация службы на корабле, боевая подготовка экипажа легли на плечи Грешилова, с чем он прекрасно справился. После такой проверки на зрелость для Михаила Васильевича не составило никакого труда сдать экзамены в командирский класс Учебного отряда подводного плавания и оказаться одним из лучших в своем выпуске. Так летом 1940 года он стал командиром новейшей «малютки» М-35 XII серии.
О «малютках» у нас писалось многократно, но либо хорошее, либо вообще ничего. В 30-х же – 40-х годах среди подводников ходила поговорка «Кто на «малютке» не бывал, тот и горя не видал». Созданная для несения прибрежной дозорной службы подлодка имела весьма неказистые размеры (206 тонн надводного водоизмещения, 44,5 метра длины) и слабые боевые характеристики (два торпедных аппарата без запасных торпед, 45-мм пушка). Экипаж состоял всего из 18 человек, в том числе трех комсостава. Лишь в первые месяцы войны в помощь им ввели четвер того командира, поскольку наличным составом нести ходовую вахту было очень тяжело (механик вахту не нес, а командиру и штурману лодки приходилось менять друг друга на вахте через каждые 4 часа, пока подлодка находилась в море). Условия обитаемости также оставляли желать много лучшего. Один из командиров субмарин военного времени Николай Белоруков так вспоминал свою службу на «малютке»: