О ранних годах жизни Михаила Стадухина известно очень мало. По одной из версий он родился в деревне на р. Пинеге. Его дядя был московским купцом. Сам С. был помором. Десять лет отдал службе казаком на берегах р. Енисей, затем – на р. Лене.

Экспедиция на Колыму

Зимой 1641 г. С. было поручено возглавить отряд для разведки новых территорий. Группа конным маршрутом прошла по северной части хребта Сунтар-Хаят и оказалась в бассейне р. Индигирки. С. у Оймякона произвел сбор ясака с якутов и двинулся к устью р. Момы, обследовав ее низовья. Вернувшись к устью Индигирки, отряд летом 1643 г. впервые вышел к р. Колыме, открыв 500 км побережья Северной Азии и Колымский залив.

Во время плавания С. увидел большой участок суши. Это способствовало рождению почти на сто лет легенды о «великой земле» в Северном Ледовитом океане.

Поднявшись по р. Колыме в ее среднее течение и открыв восточную окраину Колымской низменности, С. основал здесь первое русское зимовье, которое должно было заниматься сбором ясака. Весной 1644 г. появилось второе зимовье. Так возник Нижнеколымский острог. В ноябре 1645 г. отряд вернулся в Якутск. Однако С. встретили неприветливо, не заплатив за службу.

Новые экспедиции

Два года исследователь находился в Якутске. В 1647 г. он предпринял новую экспедицию вниз по р. Лене. В марте 1648 г. на нартах он пошел к р. Индигирке. Спустившись к ее устью, морем вышел к Нижнеколымскому острогу. Летом 1649 г. С. решил дойти до Чукотки, но этим планам не суждено было сбыться. Возвратившись на Колыму в сентябре, он начал подготовку сухопутного похода на Анадырь, которое растянулось почти на десятилетие.

В 1650 г. на Колыме состоялась встреча В.Е. Бугора и С. Оба отряда отправились на р. Анадырь по суше. Морским путем С. дошел до устья Гижиги, где встал на зимовку. Осенью 1652 г. он оказался в устье р. Тауй, воздвиг там острог, приступил к сбору ясака.

Во время поездки состоялась его встреча с С.И. Дежневым, с которым он поспорил из-за ясака.

Летом 1657 г. группа С. вышла к устью Охоты, а летом 1659 г. через Оймякон и Алдан возвратилась в Якутск, пройдя огромный кольцевой маршрут по Северо-Восточной Азии. С. подготовил чертеж маршрута отряда, проложенный по рекам и горам Якутии и Чукотки, а также путь у берегов Восточно-Сибирского и Охотского морей. Были подготовлены материалы об островах Северного Ледовитого океана и Беринговом проливе. С. первым посетил Камчатку.

За двенадцать лет странствий С. прошел и открыл 1500 км северного побережья Охотского моря.

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