Заложена 25 октября 1937 года на заводе № 112 (Красное Сормово) в Горьком под стапельным номером 250. 13 июня 1939 года подводная лодка была спущена на воду. Вскоре она была погружена на железнодорожный транспортер и направлена на завод № 198 в Николаев, где вступила в строй и 19 июня 1940 года вошла в состав Черноморского флота.

    Начало Великой Отечественной войны «М-59» встретила под командованием капитан-лейтенанта Матвеева Георгия Андреевича в составе 7-го дивизиона 2-й бригады подводных лодок Черноморского флота, находясь в гарантийном ремонте в Севастополе.

    С сентября 1941 года лодка начинает выходы на позицию, но уже третий боевой поход стал для «М-59» и двадцати членов её экипажа последним.

    Вероятно, подводная лодка погибла на мине в конце октября – начале ноября 1941 года в районе северо-восточнее Сулины (позиция № 18). По данным ряда источников «М-59» стала жертвой тарана и глубинных бомб румынского эсминца «Реджеле Фердинанд I» 5 ноября и даже 17 декабря 1941 года (срок автономности ПЛ истек 8 декабря) в районе Сулины, что представляется маловероятным. Вместе с кораблем погибли 20 членов экипажа подводной лодки.

    В 1991 году экипажу «М-59» на маяке острова Змеиный (Фидониси) установлена мемориальная доска.