Po udzieleniu błogosławieństwa przez garstkę przychylnych krucjacie księży, gromady dzieci wyruszyły na południe. Sam Stefan, jako przywódca, zażądał dla siebie wozu krytego baldachimem, bogato zdobionego. W nim odbywał podróż. U jego boków jechała garstka chłopców z rodów rycerskich, których stać było na konia. Reszta dzieci szła pieszo. Uczestnicy krucjaty traktowali Stefana jak świętego proroka, a pukle jego włosów i strzępy jego ubrania jak relikwie. Podczas marszu krzyżowcy żywili się tym, co dostarczała im miejscowa ludność. Jeśli jedzenia brakowało – głodowali. Wiele dzieci zmarło po drodze wskutek głodu oraz dużych o tej porze roku upałów. Kiedy doszli do Marsylii, zostali tam przyjęci serdecznie. Marsylczycy nakarmili ich i dali im noclegi – część dostała kwatery pod dachem, reszta nocowała na ulicach.
Następnego dnia morze jednak „nie chciało się” rozstąpić, jak obiecywał Stefan na początku krucjaty. W tej sytuacji część dzieci oskarżyła go o oszustwo, opuściła krucjatę i wróciła do domów. Reszta zdecydowała się czekać, aż morze się rozstąpi. Po kilku dniach dwóch marsylskich kupców Hugon Ferrus (Żelazny) i Wilhelm Porcus (Świnia) zaoferowali, że przewiozą dzieci za darmo do Palestyny. Stefan przyjął tę propozycję.