Объявив об этих решениях, он созвал крестоносцев весной 1189 года в Ратисбонн на Дунае. Его маршрут был прост. Первый этап должен был привести его, не взирая на возможные нападения местных жителей, прямо в Византийскую империю, так как Исаак Ангел согласился оказать помощь и поставить необходимое довольствие в обмен на обещание Фридриха, что никаких военных действий не будет проведено ни на греческих территориях, ни в ущерб греческим интересам. Затем второй этап — в ходе которого армия ускорит темп передвижения, сохраняя при этом боевой порядок, так как тут уже можно будет встретить вражеские войска — позволит достичь христианского государства Малой Армении у самых ворот Сирии. Тогда начнется последняя часть операции, являющаяся целью крестового похода, — вторжение на территории, захваченные Саладином.
В начале мая в Ратисбонне собралось тысяч двадцать воинов, а не более ста тысяч, как утверждали некоторые авторы хроник, неспособные перевести в реальные цифры толпы, бывшие у них перед глазами, и дабы лучше показать силу и мощь войск, склонные называть такие числа, которые людям XII века казались бесконечно большими. Впрочем, эта армия была самой многочисленной из тех, которыми когда-либо командовал Фридрих за все время своего правления. В военном отношении она представляла собой страшную силу, сформированную из воинственных рыцарей, во главе с превосходным и всеми почитаемым военачальником, окруженным советниками, в составе человек шестидесяти принцев и сеньоров.
1 мая император дал сигнал к отправлению. Армия тронулась в путь батальонами примерно человек по пятьсот. Первый этап похода прошел по предусмотренному плану. Венгрию прошли совершенно спокойно, так как король Бела выполнил свои обязательства и высказал тем большую готовность помогать немцам, что Фридрих попросил у него руки его дочери для своего сына Фридриха Швабского. В Сербии тоже все прошло прекрасно, и великий жупан далее предложил Штауфену принять его княжество под свой императорский сюзеренитет. Однако трудности возникли, когда за Нишем войска вошли в теснины, поднимающиеся от долины Моравы и вновь спускающиеся к Марице и окрестностям Софии. Там на них напали сербские и болгарские разбойничьи отряды и преградили им дорогу. Тут оказалось, что маршрут не может быть выдержан в точности, не хватает продовольствия, многие рыцари ослабели из-за болезней. Вместе с тем, ситуация была не настолько серьезна и, когда в начале августа войско вышло к византийским границам, для пессимизма не было оснований.
И вот здесь появились настоящие опасности, порожденные политикой Исаака Ангела. Когда Штауфен обратился к нему за поддержкой, он не смог отказать; но на самом деле у него не было намерения действительно помогать западной экспедиции. С одной стороны, он действительно и с полным основанием опасался вымогательств и репрессий немецкой военщины, оставившей ужасную память о своем походе через Византию в 1147 году. С другой стороны, он боялся — напрасно, впрочем — что Барбаросса, мечтающий, как считал Ангел, о мировом господстве, может воспользоваться своим походом для захвата греческой территории и станет единоличным монархом-императором. К тому же Ангел проводил собственную восточную политику; он старался расширить свои владения за счет султаната Коньи и в этих целях установил контакты с Саладином. Саладин хитро дал понять, что готов признать права Византии на святую землю (протекторат учреждений, привилегии), исключающие права любой другой державы, если греки не будут участвовать с Коньей, утверждая, что единственное реальное спасение, которого она может ожидать от христиан, кем бы они не были, это спасение, исходящее от него.
Может быть, Барбаросса и не был бы удивлен поведением Исаака. Кроме того, он знал, что византийские греки не могут испытывать к немцам никаких дружественных чувств. Но, если он никогда не собирался завоевывать Византию, тем более сейчас, когда вся его энергия была устремлена на достижение Святой земли, он не хотел быть стесненным политическими интригами. Поэтому он строго придерживался своего плана.