Фридрих отвел целый год на приготовления, включавшие в себя широкую дипломатическую подготовку крестового похода, дабы избежать нежелательных трений и потерь на пути в Святую землю. Было отправлено несколько посольств. По рыцарскому обычаю, от султана Саладина сперва потребовали освободить Святую землю, возвратить захваченное в качестве трофея копье Христа (Священное копье) и выпустить из неволи захваченных в плен христиан. Если он откажется выполнить предъявленные требования, то ему объявлялась война. С этой целью к Саладину был направлен во главе посольства граф Генрих фон Диц. Прямо с Майнцского хофтага архиепископ Конрад Майнцский отправился к королю Венгрии Беле, чтобы вести с ним переговоры о мирном прохождении через его владения и договориться о снабжении крестоносцев. Король дружески принял посольство, пообещав крестоносцам всяческую поддержку. Фридрих, очевидно, знал о натянутых отношениях между Саладином и правителем Иконийского султаната Килич Арсланом, поскольку ко двору последнего также отправилось посольство для ведения переговоров о мирном прохождении и снабжении. Тогда же был установлен контакт и с Леоном II, правителем армянского государства в горах Тавра. Предметом переговоров было оказание поддержки крестоносцам. Сам папа Климент III обратился к Леону II и армянскому патриарху Григорию VII с просьбой о помощи святому воинству.
Однако наибольшее значение имели переговоры с византийским императором Исааком II Ангелом. Первую попытку заключить с ним соглашение Фридрих предпринял сразу же после Майнцского хофтага, направив посольство в Константинополь. На рейхстаге в Нюрнберге, который император проводил в начале 1189 года, появилось посольство Исаака во главе с логофетом Иоанном Дукой. По требованию логофета, Фридрих велел своему сыну герцогу Фридриху Швабскому, а также герцогу Леопольду Австрийскому и епископу Готфриду Вюрцбургскому засвидетельствовать торжественной клятвой мирный характер своих намерений в отношении Константинополя. После этого посол обещал беспрепятственное прохождение через территорию Болгарии, мирный прием в Византийской империи, снабжение и переправу на греческих судах через Геллеспонт. Эти обещания он засвидетельствовал клятвой на Евангелии, после чего упомянутые немецкие князья еще раз поклялись, что крестоносное войско, совершая марш по территории Византии, будет соблюдать мир и порядок. Тогда же была намечена отправка в Константинополь нового посольства в составе епископа Германа Мюнстерского, графов Рупрехта и Вальрама Нассауских, Генриха фон Дица и Маркварта фон Нойенбурга с большим отрядом рыцарей.
И в отношении Иконийского султаната дипломатическая подготовка крестового похода принесла результат: в Нюрнберге появилось посольство от султана Килич Арслана, обещавшее поддержку крестоносцам во время марша по Анатолии. Прибыло и посольство от великого жупана Сербии Стефана Немани, велевшего передать, что с радостью ждет прибытия императора и что его стольный град Ниш готов к торжественному приему крестоносного войска. Наконец приехали и представители от султана Саладина, сперва ответившего на вызов Фридриха столь же смелым вызовом, но затем обратившегося с небезынтересным предложением: в обмен на сдачу последних принадлежавших христианам городов в Сирии он предлагал возвратить некоторые христианские монастыри и Священное копье, освободить военнопленных, разрешить христианское богослужение в церкви Гроба Господня в Иерусалиме и обеспечить беспрепятственный доступ христианским паломникам к святым местам. Император никак не прореагировал на эти предложения, поскольку царившее среди крестоносцев настроение уже делало невозможным компромиссы, а сдача сирийских городов не входила в сферу его компетенции.
Во время пребывания Фридриха в пфальце Хагенау в апреле 1189 года, очевидно, были достигнуты окончательные соглашения с церковью, касавшиеся крестового похода, здесь же он взял сумку и посох паломника. В Хагенау он в последний раз собрал всех своих пятерых сыновей: Фридриха, Генриха, Отто, Конрада и Филиппа. Старший отправлялся вместе с ним в крестовый поход, а Генрих должен был взять в свои руки бразды правления Империей. В середине апреля Барбаросса отправился в Регенсбург, где 1 мая открыл рейхстаг. Окончательной датой начала крестового похода было намечено 11 мая. Войско, численно превосходившее любое из тех, что Барбаросса водил в Италию, к тому времени собралось. И все же к разочарованию императора в нем отсутствовали многие из тех, кто дал обет участия в крестовом походе.
В окружении императора особенно важную роль играли Фридрих Швабский как военный предводитель и Готфрид Вюрцбургский (епископ и одновременно герцог Франконии) в качестве советника, стратега и идейного вдохновителя. Наряду с самим императором он пользовался наибольшим авторитетом среди крестоносцев. Численность войска составляла далеко не 100 тысяч человек, как сообщают некоторые источники, а от силы тысяч 15, из которых около трех тысяч — рыцари с полным вооружением и оснащением, а остальные — оруженосцы и слуги, почти все вооруженные и на конях. Вплоть до переправы через Геллеспонт за войском должен был следовать большой обоз из телег, нагруженных оружием, провиантом, палатками и прочим скарбом. В Малой Азии все это предполагалось перегрузить на лошадей и мулов. Барбаросса, сделавший для подготовки крестового похода все, что в силах смертного человека, порой сомневался, достаточно ли этого для успешного завершения задуманного, но отступать было уже поздно.
11 мая 1189 года Барбаросса, передав власть в Империи своему сыну Генриху VI, выступил из Регенсбурга во главе крестоносного войска. Сам император и наиболее знатные участники похода плыли на судах по Дунаю, тогда как вереница крестоносцев двигалась по суше вдоль реки. Когда они прибыли в Пассау, к войску присоединился и местный епископ со своей дружиной. Дальше дорога вела по территории Австрии. Жители оказавшегося на их пути Маутхаузена потребовали от них обычную дорожную пошлину, как будто имели дело с купеческим караваном. Взбешенные столь беспримерной дерзостью крестоносцы разгромили и сожгли обиталище нечестивых мытарей.
22 мая Христово воинство прибыло в Вену, где герцог Леопольд V Бабенберг с большой свитой вышел навстречу императору и устроил ему великолепный прием. Леопольд, за несколько лет до того уже совершивший паломничество в Иерусалим и даже собравший собственное крестоносное войско для осады Акры, не смог присоединиться к Барбароссе из-за враждебных отношений с Венгрией, со стороны которой в любой момент можно было ждать нападения. Однако он щедро обеспечил крестоносцев провиантом, подтвердив свою славу гостеприимного хозяина. Император, следивший за порядком в войске, заставил вернуться назад около полутысячи мнимых паломников, очевидно, бродяг и уголовников, увязавшихся за крестоносцами в надежде на поживу. На участке пути от Вены до Пресбурга герцог Леопольд предоставил императору почетное сопровождение.
