За три недели казаки по тяжелой дороге прошли 700 верст. Многие умирали от болезней и холода. Падеж лошадей усилился. В войске поднялся ропот, были даже случаи открытого неповиновения не только среди рядовых казаков, но и среди офицерства. Все стали просить Матвея Ивановича вернуться на Дон.
Наконец 23 марта, когда передовые отряды войска уже достигли верховьев Иргиза (в селе Мечетном Вольского уезда Саратовской губернии), гонец из Петербурга догнал их и объявил о смерти Павла I и восшествии на престол нового государя — Александра I, который повелел донцам вернуться на родину.
Так окончился этот поход.
Вскоре умер атаман Войска Донского В. П. Орлов. По возвращении на Дон рескриптом от 12 августа 1801 года генерал-майор Платов был назначен атаманом Войска Донского. «Известные ваши достоинства и долговременная и безупречная служба, — указывалось в рескрипте, — побудили меня избрать вас в войсковые атаманы Войска Донского на место умершего генерала от кавалерии Орлова».
У нового атамана сразу же появилось много забот по внутреннему устройству края. Первое, что решил сделать Платов, — перенести казачью столицу на новое место: Черкасск ежегодно затоплялся водой, что, естественно, затрудняло административную, политическую и хозяйственную деятельность городка. Но это был всего лишь повод. Старая столица донских казаков уж больно прославилась своим мятежным прошлым. Еще памятны были среди казачества легенды о Разине, Булавине…
Чтобы решить, куда переносить новую столицу, в 1804 году на Дон прибыл инженер де Волан. Тогда же создали специальную комиссию по устройству новой столицы.
Осенью 1804 года комиссия осмотрела ряд мест, пригодных для основания новой столицы, в том числе Аксайские и Черкасские бугры, Заплавскую и Манычскую станицы. Решено было остановиться на урочище Бирючий Кут — возвышенности, расположенной между реками Аксай и Тузлов.
7 ноября 1804 года Платов и де Волан представили Александру I доклад и план будущего города. К плану прилагалось описание улиц, площадей, где должны располагаться соборная и ряд других церквей, войсковая канцелярия, гимназия, гостиный двор, лазарет. 31 декабря 1804 года Александр I утвердил эти документы.
Для строительства Нового Черкасска — так назвали новую столицу — был назначен производитель работ инженер-капитан Ефимов, до этого руководивший высыпкой дамб в Старом Черкасске, как стали называть казаки бывшую свою столицу.
Под его команду было отдано два полка казаков. Многие из них участвовали в строительстве новой столицы в качестве мастеров и рабочих. К делу привлекли малороссиян, приписанных к станицам.
18 мая 1805 года по приказу Платова более тридцати станиц с воинскими регалиями и знаменами вызвали для участия в церемонии закладки новой столицы. От каждой станицы при закладке присутствовало по три подростка.
Прежде всего был заложен войсковой Вознесенский собор. В позолоченный ларец опустили серебряную доску с надписью: «Город Войска Донского, именуемый Новый Черкасск, основан… лета от Рождества Христова 1805-го 18 дня, который до сего существовал 235 лет при береге Дона на острове, от сего места прямо на юг расстоянием в 20 верст под названием Черкасска».
Затем были заложены Александро-Невская церковь, гостиный двор, войсковая канцелярия, гимназия.
В конце дня начались гулянья. В огромном шатре, специально установленном накануне празднества, накрыли столы для трехсот человек. Здесь пировали самые почетные гости во главе с Платовым. Остальные участники закладки гуляли под открытым небом. Торжества сопровождались обычными казачьими состязаниями.
19 мая произошло торжественное перенесение столицы из Старого Черкасска в Новочеркасск. Переезд совершался по залитой водой пойме Дона. Под звон колоколов разжалованного города процессия погрузилась на лодки и плоты и взяла курс на Бирючий Кут. На головной лодке везли воинские знамена и регалии, дарованные казакам за их подвиги в войнах. За ней следовала лодка с духовенством, затем с атаманом. Далее сплошной вереницей тянулись лодки со станичниками.
Проделав почти 20 верст пути, они причалили к специально построенной пристани. У временной войсковой канцелярии состоялось провозглашение новой столицы. Гулянья продолжались не один день.