Не чекаючи закінчення трьох днів, милостиво дозволених йому в Петрограді, гетьман вирушив на Дон, де його прийняли як повернутого з мертвих. Припиняючи всі демонстрації привітання, він негайно почав збирати війська войовничої громади, однак не розкриваючи мети погано спланованої кампанії, до якої вони мали виступити. Кожному козаку, здатному носити списа, наказувалося з’явитися на певне побачення, взявши з собою двох коней і провіант на шість тижнів. У січні 1801 року 27 500 донських козаків змогли вирушити в далекий похід до пустель Азії.
В Оренбурзі російський губернатор Бакметієв зібрав провіант, верблюжий транспорт і навіть загін перекладачів, що розмовляли мовами чи діалектами численних племен, країнами яких вони мали подолати. Перед їх відходом із фортеці було зачитано листа Павла, який обіцяв козакам «всі багатства Індії». Сміливо кинувшись у майже бездоріжну пустелю, що лежала за прикордонними заставами, російські війська мандрували, як мореплавці, по невідомому морю, маршируючи, вірніше орієнтуючись, за компасом і спостерігаючи за положенням зірок.
На обрії зависли великі загони вершників, башкирів і калмуків, вражені, побачивши настільки численні війська, що їх не можна було атакувати жодною відомою тактикою війни в пустелі.
Не боячись несподіванки чи засідки, війська йшли невимушено й у відкритому порядку. Але тепер козацькому війську загрожувала інша небезпека. Коли про віддалену мету походу поширилися чутки, киргизькі погоничі верблюдів почали дезертирувати зі своїми тваринами, позбавивши росіян єдиного транспортного засобу. Довелося навіть відмовитися від значної частини провіанту, наметів та іншого необхідного військам спорядження. Крім того, через сильні холоди запаси палива швидко зникали. Козаки, які не звикли до економії в цьому відношенні, наполягали на тому, щоб довгими холодними ночами розпалювати вогнища. Хвороба також спалахнула в рядах, і проблема транспортування тих, хто вже не міг залишатися в сідлі, додала Платову труднощів. За відсутності будь-яких розпізнаних знаків у невиразному краєвиді одноденний марш видався нетерплячим і напівзбунтованим військам точно таким же, як і попередній. Пустельний міраж, надзвичайно яскравий у цих широтах, показав їм куполи далеких міст і оазисів, які вони вважали Хівою чи Бухарою, і наступної миті розчинив ці мальовничі сцени в хмарах туману. Такі явища посилювали забобонні страхи козаків. ^Слани заявив, що все військо зачароване татарськими чаклунами і що всі вони йдуть вперед, не просуваючись до своєї мети.*
* Старий атавістичний страх перед татарами породив серед мужиків і козаків прикордоння