Заложена 31 августа 1938 года под стапельным номером 258 на заводе № 112 (Красное Сормово) в Горьком. Вскоре подводная лодка была погружена на железнодорожный транспортер и направлена на завод № 198 в Николаев, где 25 февраля 1940 года она спущена на воду. 31 октября 1940 года субмарина вступила в строй и 7 ноября 1940 года вошла в состав Черноморского флота.Первым командиром корабля стал Зубков Федор Антонович.

    22 июня 1941 года «М-31» командовал старший лейтенант (впоследствии капитан-лейтенант) Расточиль Евгений Генрихович. Подводная лодка входила в состав 7-го дивизиона 2-й бригады ПЛ ЧФ в Севастополе.

    С началом Великой Отечественной войны «М-31» выходит на дозорные позиции юго-западнее мыса Сарыч и юго-восточнее Одессы, где встреч с кораблями противника не имела. С начала сентября субмарина привлекается к действиям на вражеских коммуникациях. Вечером 4 сентября, маневрируя в подводном положении на внешнем рейде Констанцы (позиция № 11), «М-31» подорвалась на одном из минных защитников румынского минного заграждения. Это вынудило субмарину вернуться в базу, так как в результате взрыва на подводной лодке оказались деформированы волнорезы торпедных аппаратов и повреждена обшивка цистерны главного балласта. После проведения аварийного ремонта «малютка» имела краткосрочный выход в дозор на подходы к Поти, после чего ее ставят на проведение текущего ремонта с заменой аккумуляторной батареи. В начале января 1942 года «М-31» вступила в строй. Во второй половине января подводная лодка патрулировала в районе Одессы (позиция № 25), а с 30 января у острова Фидониси. 2 февраля субмарина от удара о плавучую льдину повредила головку перископа, и ей пришлось покинуть район действий и вернуться в Севастополь.

    После проведния текущего ремонта «М-31» привлекают к снабжению защитников Севастополя. С 16 июня по 1 июля подводная лодка совершила три транспортных рейса, доставив бойцам Севастопольского оборонительного района 15,9 тонн боеприпасов, 5,7 тонн продовольствия, 5,5 тонн бензина. В Новороссийск на борту субмарины было доставлено 12 человек и эвакуируемый груз (всего порядка 2300 кг), в том числе ценности государственного банка и сберегательных касс на сумму 14.456.430 рублей, а так же ордена.

    В середине июля «М-31» патрулировала район у Тарханкута, но кораблей и судов противника не обнаружила. Первая встреча с противником состоялась лишь днем 17 августа (в ходе первого транспортного рейса в Севастополь днем 16 июня, когда «М-31» возвращалась в Новороссийск, подводная лодка в 5 милях южнее Мысхако якобы обнаружила вражескую субмарину, но, скорее всего, это был ложный контакт). Патрулируя район на подходах к Одессе (позиция № 31, в точке 46°19,9' с.ш./30°45,8' в.д.), «М-31» обнаружила конвой противника. Подводная лодка выпустила по одному из транспортов две торпеды, но по воздушному пузырю была обнаружена одним из кораблей эскорта, который сбросил в предполагаемом месте нахождения субмарины глубинные бомбы. (Информация о том, что в ходе этой атаки субмариной потоплен буксир «Дюренштейн» в 300 тонн не соответствует действительности). Израсходовав боезапас и получив повреждения в результате контратаки (крышка верхнего рубочного люка, перископ, рулевое управление), подводная лодка в ночь на 18 августа начала возвращение в Очемчири.

    Следующий боевой поход принес «М-31» первый успех. 5 октября подводная лодка прибыла в назначенный район у мыса Бурнас (позиция № 42), а уже вечером 6 октября выпустила торпеды по вражескому конвою из барж под охраной сторожевых катеров. Субмарина атаковала в надводном положении, поэтому находящиеся наверху в боевой рубке могли наблюдать два взрыва, а затем еще один более сильный взрыв. Не погружаясь, «М-31» развернулась и на полном ходу покинула место боя, в результате которого в точке 45°47,4' с.ш./30°19,0' в.д. потоплен румынский буксир «Олтул» (50 брт, бывший итальянский тральщик «RD-1», проданный Румынии в 1921 году), на котором погибло 10 человек.

    В следующем боевом походе подводной лодке вновь предоставлялась возможность поразить цель, но торпеды, выпущенные днем 4 ноября в точке 45°47,8' с.ш./30°10,7' в.д. (пределы позициии № 42) прошли мимо румынского вооруженного буксира «Бессарабия».

    В последний боевой поход «М-31» вышла вечером 14 декабря 1942 года. На связь она не выходила и в базу не вернулась. По данным противника в 21.52. 17 декабря в бухте Жебрияны речной катер-тральщик «FR-2» из состава эскорта конвоя обнаружил советскую субмарину в надводном положении и заставил ее погрузиться. Подошедший большой охотник «Uj-116» («Ксантен») и катера-тральщики установили контакт с неподвижно стоящей на небольшой глубине субмариной и сбросили три десятка глубинных бомб, после чего на поверхности воды появились маслянные пятна. К полуночи катера «FR-7», «FR-8» и тральщик «R-30» с помощью лотов обнаружили корпус подводной лодки, после чего по этому месту прошелся с глубинными бомбами «Ксантен». После бомбардировки противник наблюдал признаки гибели субмарины – всплывшие обломки и различные предметы. На «М-31» погиб 21 член экипажа.