Заложена 22 февраля 1939 года под стапельным номером 270 на заводе № 112 (Красное Сормово) в Горьком. 28 августа 1940 года подводная лодка спущена на воду. Вскоре она была погружена на железнодорожный транспортер и направлена на завод № 198 в Николаев, где 20 февраля 1941 года вступила в строй и 29 апреля 1941 года вошла в состав Черноморского флота.

    22 июня 1941 года «М-36» встретила в составе 8-го дивизиона 2-й бригады ПЛ ЧФ в Севастополе. Командовал субмариной старший лейтенант (впоследствии капитан-лейтенант) Комаров Валентин Николаевич, который вступил в эту должность в июне 1940 года.

    В середине июля – середине августа 1941 года подводная лодка несла дозор в районе северо-восточнее острова Фидониси (позиция № 6), после чего выходила на позиции западнее Бураса (позиция №16) и у Сулины (позиции № 17 и № 18). В ноябре – декабре «М-36» привлекалась к несению дозора у Поти. В январе – феврале 1942 года субмарина два раза выходила в район Евпаторя – Лукулл с задачей ведения разведки. Первый контакт с противником состоялся вечером 8 марта 1942 года, когда «М-36» в ялтинском порту атаковала баржу, но промахнулась. Торпеда взорвалась при ударе о причал.

    Во второй половине июля подводная лодка находилась в районе Алушта – Судак, но вновь противника не встретила.

    В ночь на 17 августа «М-36» вышла из Очемчири в свой двенадцатый боевой поход. Подводной лодке предстояло действовать севернее острова Фидониси (позиция № 32). На переходе субмарина была встречена крейсером «Красный Кавказ», который, не заметив опознавательного сигнала атаковал погрузившуюся подводную лодку, безрезультатно сбросив на нее 2 глубинных бомбы. Прибыв на позицию, вечером 23 августа восточнее мыса Бурнас субмарина обнаружила конвой противника, шедший по мелководью. Выходя в атаку «М-36» несколько раз касалась грунта, а перед выпуском торпед в течение четырех минут буквально ползла по грунту.

    После того, как торпеды устремились к цели, подводная лодка не удержалась на глубине и была выброшена на поверхность. Обнаружив «М-36» румынская канонерская лодка «Гикулеску» нанесла ей таранный удар, а после того, как подводная лодка легла на грунт на глубине всего восьми метров, забросала её глубинными бомбами. От взрыва на «М-36» сорвало задрайку люка VI (электромоторного) отсека, он начал быстро заполняться водой и личный состав был вынужден его покинуть. На подводной лодке вышли из стоя главные электродвигатели, трюмная помпа, компрессор и кормовые горизонтальные рули. Корпус «М-36» так же получил тяжелые повреждения: погнуты перо вертикального руля, три лопасти гребного винта, а так же оторван лист киля. Противник, посчитав лодку потопленной, прекратил бомбометание и ушел с места боя, а субмарина всплыв направилась в базу, в пути отразив четыре атаки вражеского самолета-торпедоносца.

    Результатом атаки «М-36» 23 августа 1942 года стало уничтожение германского буксира «Анкара» в 112 брт, который затонул в точке 45°49,2' с.ш./30°12,5' в.д. По данным некоторых советских источников это судно оценивается как достаточно большой теплоход водоизмещением в 4.768 брт. По информации руководителя клуба «Нептун-Про» из Тольятти А. Елкина, «Анкара» – трофейная грузоотовозная шаланда «Ангара» (с машины судна снят прибор с надписью «Кiев. Завод точных приборов»). Судно длиной 50-60 метров лежит на дне перевернутое вверх килем, в носу пробоина диаметром 6-7 метров.

    В октябре 1942 года «М-36» выделили к переброске на Северный флот. В середине ноября подводная лодка была погружена на железнодорожный транспортер и 24 ноября отправлена в Баку, куда благополучно прибыла через пять суток. В начале декабря 1942 года на территории завода имени Закфедерации в Баку «М-36» была спущена на воду, и 13 января 1943 года зачислена в состав Каспийской военной флотилии.

    Вскоре от перебазирования «М-36» на Север отказались. Подводная лодка отправлена в Поти, и 16 октября 1943 года она вновь включена в состав Черноморского флота.

    В ночь на 4 января 1944 года «М-36» вышла в Кобулети на мерную милю для испытания механизмов и проверки надводной скорости. До 05.00 с подводной лодкой поддерживалась радиосвязь, когда она доложила о включении огней Кабулетской мерной мили. В дальнейшем субмарина на связь не выходила и в базу не вернулась. В 07.46. с поста «№ 4», куда должна была перейти «М-36» на поиск субмарины вышел сторожевой катер «№ 041», но подводную лодку не обнаружил. (В поисках «М-36» были задействованы в общей сложности два десятка различных кораблей и судов, в том числе подводная лодка «С-31», авиация). С береговых постов ее не видели и взрывов в море не слышали. Поиск подводной лодки, предпринятый 6-8 января показал, что в районе 41°58,8' – 41°59,3' с.ш./41°40' – 41°42' в.д. обнаружены масляное пятно, буек и плавающий ящик. (К западу от поста «№ 4», глубина моря в этом месте 415 м). Вероятно, субмарина погибла в результате аварии. Среди причин гибели «М-36» могли быть: ошибка личного состава при проведении срочного погружения в ходе уклонения от самолета или подводной лодки, авария в следствие спешно проведенных монтажных работ либо подрыв на плавающей мине. Версия о том, что подводная лодка стала жертвой минной постановки германской субмарины «U-20», не соответствует действительности, так как немецкая подлодка выставила минную банку из 9 мин «ТМВ» между точками 42°12,9' с.ш./41°38,0' в.д. и 42°13,1' с.ш./41°36,9' в.д.

    Вместе с «М-36» погибло 24 человека.