Szeremietiew oraz główne siły ruszyły wiosną. W skład wojsk idących na Azow wchodziły jednostki doborowe: pułki preobrażeński, siemionowski, butyrski Patryka Gordona oraz pułk Leforta, a także strzelcy moskiewscy oraz zawodowe jednostki tzw. żołnierzy grodowych. Sztab dowodzenia składał się z trzech generałów: Leforta, Gordona oraz dowodzącego pułkiem preobrażeńskim Awtamona Gołowina. Car wziął udział w stopniu bombardiera i dowodził tylko rotą.
Maszerujące siły, gdy tylko było to możliwe, płynęły rzekami, unikając marszu lądem. Armia załadowana została na łodzie w stolicy i ruszyła na południe, płynąc rzekami Moskwą, Oką i Wołgą do Carycyna. Pierwsze poważne trudności napotkano dopiero przy przeprawie lądowej prowadzącej do rzeki Don, gdzie z powodu braku koni przeładowani nadmiarem broni i sprzętu żołnierze posuwali się bardzo wolno, co znacznie wydłużyło czas podróży. Z kolei nad Donem okazało się, że zgromadzone zapasy żywności są niewystarczające.
Armia rosyjska po wielu trudach dotarła pod Azow 9 lipca – czyli dokładnie w dniu carskich imienin. Na miejscu spotkano siły Gordona, który maszerował lądem z Tambowa przez Czerkask.