Византийские власти с беспокойством следили за происходящим. Отношения между императорами Востока и Запада были, как мы помним, не лучшими со времен Карла Великого. Василевсы не желали признавать императорский титул за какими-то «варварами», императоры Запада и римские папы не оставляли надежд на воссоединение Церквей под эгидой Рима. Да и союзники Фридриха не внушали доверия в Новом Риме. Кылыч-Арслан был врагом не только Саладина, но и Ромейской державы. Стефан Неманя не только добился полной независимости от Константинополя, но еще и претендовал на некоторые земли Греческой империи. Иван Асень являлся, с византийской точки зрения, мятежником и сепаратистом, ибо добился в результате победоносного мятежа 1186 г. восстановления независимости Болгарии от Византии, уничтожившей так называемое (позднейшими историками) Первое Болгарские царство в 1018 г.
В Константинополе возникало опасение: а не собирается ли Барбаросса с помощью своих союзников захватить Византийскую империю? Некоторые хроники сообщают, что великий жупан и болгарский царь делали Фридриху предложения – признать его единственным законным императором в мире, помочь свергнуть греческих владык, конечно же, за значительные территориальные уступки в пользу Сербии и Болгарии. Если это правда, то указанных государей не смущало, что византийские правители были их единоверцами – православными, тогда как император – католиком. Ответ Барбароссы (если он вообще последовал) нам неизвестен. Однако предположение (конечно, только предположение) о том, что император захочет увенчать свой жизненный путь не только отвоеванием Иерусалима, но и восстановлением единой Римской империи, не лишено смысла.
Не лишено также смысла и другое предположение, подтверждаемое некоторыми, правда, позднейшими хронистами, о том, что Саладин предлагал ромеям то же, что он предлагал Барбароссе, при условии, что они откажутся от любых контактов с Румским султаном, а равно не признают никаких прав франков на Святую Землю.
Все это объясняет трудности похода, превратившегося в военную экспедицию еще до вступления в Палестину. Даже более или менее союзные сербы и болгары без восторга встречали крестоносцев, в которых видели еретиков-католиков, а также – по большей части вполне справедливо – грабителей. Еще сложнее было пройти через Ромейскую державу. Там шли настоящие военные действия. Пробиваться приходилось с боями. 24 августа 1189 г. армия Барбароссы вошла в Филиппополь, заняла ряд укрепленных пунктов около города и захватила продовольственные склады в нем. На следующий день посланцы Исаака Ангела передали Фридриху требование василевса оставить ему заложников и поклясться уступить часть будущих завоеваний, если Барбаросса собирается продолжать свой путь. Тот не согласился, но отправил владыке Восточной империи послов, каковых Исаак повелел бросить в темницу. Рассвирепев, Краснобородый приказал своей армии идти на Константинополь, предавая на своем пути все огню и мечу. В конце октября он овладел Адрианополем, а 16 ноября 1189 г. даже написал своему сыну Генриху, будущему императору Генриху VI, оставшемуся наместником Западной империи, чтобы тот снарядил флот и послал подкрепление, а также убедил Папу объявить крестовый поход против Греческого царства. Иначе, считал Барбаросса, не удастся переправиться через Босфор и пойти в Святую Землю. До этого, однако, не дошло.
Наконец, 21 января 1190 г. оба императора заключили соглашение, в соответствии с которым Фридрих обещался не идти на Константинополь, а Исаак отказывался от своих требований. 24 февраля они подписали окончательный договор, по которому крестоносцы 25—29 марта были переправлены в Малую Азию. Поход по Малой Азии тоже оказался нелегким. Христиан встретили засушливые земли и враждебное местное население. На территории Иконийского султаната на них непрерывно нападали отряды турок, несмотря на все договоренности с Кылыч-Арсланом (то ли султан вел двойную игру, то ли турки не спешили выполнять приказы своего повелителя, ставя борьбу с неверными выше долга подданных). Тем временем в самом султанате произошел переворот. Сын Кылыч-Арслана Кутб-ад-дин отрешил отца от власти и стал требовать от крестоносцев деньги за проход по стране. Пришлось прорываться с боями. 18 мая 1190 г. была взята Конья, она же Иконий, причем победоносную атаку на совершившую вылазку турецкую конницу возглавлял сам престарелый император. Наконец, 10 июня 1190 г. войско достигло протекающей в южной части Малоазийского полуострова горной речки Салеф. По нелепой случайности император погиб при переправе через нее.