28 июня 1763 года Степан Ефремов участвовал вместе с отрядом донцов в походе на Петергоф, в результате чего на российском престоле оказалась Екатерина II. За деятельное участие в этом походе Степан Ефремов был «всемилостивейше» награжден императорской золотой медалью.
Екатерина II не забыла тех, кто помог ей прийти к власти, и с ее покровительства Степан Ефремов почувствовал неограниченную власть на Дону, что способствовало его быстрому обогащению, часто незаконному.
Скоро вести о его многочисленных злоупотреблениях дошли до двора. Екатерина II была вынуждена назначить комиссию по проверке деятельности атамана. На Доп посыпались приказы из Военной коллегии о том, чтобы Ефремов незамедлительно прибыл в Петербург. Атаман ехать не спешил, тянул время и пытался распространять среди казаков слухи, будто правительство хочет записать их в «регулярство».
Назревал бунт.
Тогда правительство снарядило на Дон отряд регулярных войск под командованием поручика Ржевского, который и арестовал Степана Ефремова на его загородной Зеленой даче. Атаман был заключен в крепость святителя Дмитрия Ростовского, а оттуда доставлен в Петербург.
Следственная комиссия выяснила, что Ефремов получал взятки за производство казаков в старшинский чин, растрачивал крупные суммы войсковых денег. Самым же главным явилось обвинение в стремлении одновластно править Доном. За все эти преступления Степан Ефремов был приговорен к смертной казни. Но Екатерина II, памятуя «Петергофский поход» донского атамана, заменила смертную казнь ссылкой в Перцов (Прибалтика).
Платов женился на дочери опального атамана именно в это время, когда Ефремов находился в ссылке.
Вначале были смотрины; Матвей Иванович под благовидным предлогом с тремя родственниками пришел в дом невесты. Надежда Степановна понравилась старшим, и они многозначительно сказали: «Бог даст, она и нас полюбит».
Через несколько дней Матвей Иванович прислал к Ефремовым своих сватов. Получив согласие родителей, сваты ушли с рукопожатиями и словами: «В добрый час!»
А затем жених и невеста прошли «сговор», во время которого все веселились, пили вино, танцевали «Казачка» и «Журавель».
За два дня до свадьбы смотрели приданое, празднуя, как говорили казаки, «подушки». Накануне торжества для невесты и ее подружек устроили девичник.
Свадьба праздновалась в воскресенье. Невесту обрядили в брачную одежду — богатый парчовый кубилек и такую же рубаху. На голову надели высокую шапку из черных смушек с красным бархатным верхом, убранным цветами и перьями, а также лучшими украшениями из золота.
Матвей Иванович, празднично одетый, получив родительское благословение, вместе со священником, дружками и свахами пошел в дом невесты.
Из дома молодые отправились в церковь, скорее всего в Донскую домовую, построенную отцом невесты для своего семейства. В церковном притворе Надежду Степановну подготовили к венцу: сняв шапку, расплели девичью косу надвое. Так ее обычно носили замужние женщины.
После венчания молодых на крыльце дома Платовых встретили родители. Над головами они держали хлеб-соль. Молодые проходили, осыпаемые пшеницей, перемешанной с хлебом, орехами, мелкими деньгами.
Родители, угостив дружков, отвели жениха и невесту в брачную комнату. Появились они за столом только перед подачей жаркого…
Однако семейное счастье Платова было недолгим. Его жена умерла 45 ноября 1783 года, когда Матвей Иванович воевал на Кубани.
Долгих семь лет, с 1778-го по 1784-й, Платов участвовал в многочисленных сражениях против чеченцев, лезгин и других горских народов, постоянно нападавших на русские кордонные линии. Здесь в 1782 году он познакомился с Александром Васильевичем Суворовым, командовавшим Кубанским корпусом.
Суворов уже на Кубани увидел силу и мощь донского оружия. В одном из приказов по корпусу он писал: «Казаков обучать сильному употреблению дротика, по донскому его размеру, в атаке, сшибе и погоне». Далее а этом же приказе полководец отмечал: «Казакам непременно быть всегда дротиком вооруженным, яко наисильнейшим их оружием для поражения всякого противника».
Советы и указания Суворова Платов помнил всю жизнь.
В 1784 году Матвей Иванович вернулся на Дон.
За время его отсутствия в управлении Войском Донским произошли значительные изменения. В 1775 году, сразу же после разгрома Пугачевского восстания, по предложению Г. А. Потемкина Екатерина II издала указ, по которому военная власть на Дону отделялась от гражданской. Во главе управления военными делами был поставлен войсковой атаман, которым стал «испытанный в верности» А. И. Иловайский.