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