22 мая Христово воинство прибыло в Вену, где герцог Леопольд V Бабенберг с большой свитой вышел навстречу императору и устроил ему великолепный прием. Леопольд, за несколько лет до того уже совершивший паломничество в Иерусалим и даже собравший собственное крестоносное войско для осады Акры, не смог присоединиться к Барбароссе из-за враждебных отношений с Венгрией, со стороны которой в любой момент можно было ждать нападения. Однако он щедро обеспечил крестоносцев провиантом, подтвердив свою славу гостеприимного хозяина. Император, следивший за порядком в войске, заставил вернуться назад около полутысячи мнимых паломников, очевидно, бродяг и уголовников, увязавшихся за крестоносцами в надежде на поживу. На участке пути от Вены до Пресбурга герцог Леопольд предоставил императору почетное сопровождение.
Тогда берега Дуная большей частью еще были не заселены и покрыты дремучими лесами. Кое-где в этой малонаселенной местности встречались паромные переправы через реку. В пограничной области между Австрией и Венгрией царила напряженная обстановка, чреватая военным конфликтом. На большом удалении друг от друга над рекой возвышались бурги и укрепленные города. В конце мая крестоносцы достигли Пресбурга, у стен которого на просторном поле разбили лагерь для четырехдневного отдыха. Император разбирал споры, наводил порядок в войске и назначал мировых судей. Там же Фридрих праздновал Троицу и принял посольство от короля Венгрии Белы III.
В начале июня король Бела и его супруга Маргарет, сестра короля Франции Филиппа II Августа, встретились с императором поблизости от Грана (Эстергома). Королевская чета Венгрии сердечно принимала немецких гостей. Бела почтил Фридриха богатыми подарками и в течение двух дней развлекал его охотой. Особенно великолепен был подарок королевы: роскошный, подразделявшийся на четыре отделения дорожный шатер, подбитый изнутри пурпуром и украшенный коврами. Важным дополнением к шатру служили диван и трон из слоновой кости. Для транспортировки этого воистину королевского подарка требовались три повозки. Бела III, в то время воевавший с Венецией, сам не принял участие в крестовом походе, однако позволил отправиться в Святую землю отряду венгерских рыцарей. Кроме того, он распорядился, чтобы на всем пути следования крестоносцев по территории Венгерского королевства им оказывали почетный прием, обеспечивали провиантом, фуражом и транспортом. Помолвка сына императора, герцога Фридриха Швабского, с одной из дочерей короля Венгрии закрепила дружественные отношения двух правящих династий.
От Грана император, сопровождаемый королем Белой, плыл по Дунаю, тогда как крестоносцы маршировали по правому берегу реки. В ходе трудной переправы через Драву, приток Дуная, несколько человек на глазах у своих товарищей были затянуты в пучину бурным водоворотом. Далее путь лежал на юго-восток к реке Саве, которую крестоносцы форсировали благополучно, без потерь. Двигаясь по богатой местности и не испытывая затруднений со снабжением, они вскоре добрались до Белграда, опустошенного в ходе недавних боев между Византией и Венгрией. Отсюда до Византии было рукой подать. Переход через Венгрию состоялся при чудесной летней погоде, стоявшей и во время отдыха в Белграде. Император вершил суд, устраивал турниры и посвятил 60 оруженосцев в рыцари.
От Белграда войско двинулось вдоль Дуная на восток и 2 июля, достигнув крепости Браничево, вступило на византийскую территорию. Здесь император, сойдя на сушу, попрощался с королем Белой, опять осыпавшим его подарками, общая стоимость которых достигала 5000 марок серебра и для перевозки которых потребовались четыре верблюда. В качестве ответного подарка император передал ему весь транспортный флот, а поклажу повелел перегрузить на телеги. Византийский управляющий Браничевым радушно встретил императора, обеспечивая войско провиантом и фуражом в течение восьми дней, пока оно отдыхало. Далее крестоносцы двинулись на юг, к Нишу. Маршрут проходил по римской военной дороге, проложенной от Белграда до Константинополя, известной как «дорога Траяна» и в те времена большей частью еще находившейся в исправном состоянии. Однако вся эта лесистая местность была безлюдна, поскольку византийские власти запрещали селиться поблизости от «дороги Траяна», и небезопасна. Участились внезапные нападения на крестоносцев из лесных зарослей, отчего особенно страдали фуражиры. Несмотря на постоянную бдительность и энергичный отпор, было много жертв от пущенных из засады отравленных стрел.