Едва германская армия успела переправиться через Дунай, как посыпались беды. Сербские и болгарские разбойники нападали на отставших и заблудившихся солдат, местные крестьяне были напуганы и встречали гостей неприветливо. Германцы тут же обвинили византийцев в том, что они подстрекают вражду со стороны местных, и отказывались понимать, что Исаак просто не в силах положить ей конец. Фридрих благоразумно постарался заручиться дружбой главарей мятежников. Стефан Неманя, сербский жупан, прибыл со своим братом Страцимиром в Ниш приветствовать германского монарха, который проходил через город в июле; а вожди болгарского восстания, валашские братья Иван Асень и Петр, прислали ему письма с обещанием помощи. Известия обо всех этих переговорах вызвали вполне естественную обеспокоенность у константинопольского двора. Исаак и без того уже подозревал Фридриха в нечистых замыслах. Его прежние послы при германском дворе Иоанн Дука и Константин Кантакузин отправились встречать Фридриха, вступившего на византийскую землю, но, к ужасу их старого друга, историка Никиты Хониата, воспользовались своей миссией для того, чтобы стравить Фридриха и Исаака, которому вскоре стало известно об их происках. Пока византийцы-провожатые своими кознями раздували недоверие Фридриха к империи, уходившее еще во времена Второго крестового похода, Исаак растерял последние остатки здравого смысла. До той поры дисциплинированность германской армии и адекватная подготовка византийских властей для снабжения ее всем необходимым в дороге предотвращали возникновение каких-либо неприятных инцидентов. Но когда Фридрих вошел в Филиппополь и оттуда отправил посланцев в Константинополь договориться о проходе его войск в Азию, Исаак бросил его представителей в тюрьму, намереваясь держать их там в качестве заложников, чтобы Фридрих не позволял себе лишнего. Однако он страшно ошибся насчет германского императора, который немедленно послал своего сына Фридриха Швабского взять, со своей стороны, в заложники город Дидимотихон во Фракии и написал домой другому сыну, Генриху, чтобы тот снарядил флот, который бы вел действия против Византии, и получил благословение папы на крестовый поход против греков. Фридрих заявил, что пока пролив находится в чужих руках, крестоносцы ничего не добьются. Перед лицом опасности нападения на Константинополь германской армии совместно с западным флотом Исаак несколько месяцев изворачивался и в конце концов отступил и выпустил немецких посланцев. В Адрианополе заключили мир. Исаак вернул заложников Фридриху и пообещал дать корабли, если он поплывет через Дарданеллы, а не Босфор, а также снабжать его провизией во время прохода по Анатолии. Фридрих хотел продолжить путь в Палестину. Он смирил свой гнев и согласился на предложенные условия.
Германская армия двигалась по Балканам черепашьим ходом, и Фридрих был слишком осторожен, чтобы отправляться в Анатолию в зимнее время года. Он перезимовал в Адрианополе, а константинопольцы дрожали от страха при одной мысли о том, что он отвергнет извинения Исаака и решит-таки идти на их город. В конце концов в марте 1190 года вся экспедиция отправилась в Галлиполи на берегу пролива Дарданеллы и при помощи византийских транспортных судов переправилась в Азию, а Исаак и его подданные вздохнули с облегчением.
От азиатского берега пролива Фридрих двинулся примерно тем же путем, которым шел Александр Македонский за полтора тысячелетия до него: пересек Граник и разлившийся Ангелокомит, пока не дошел до мощеной византийской дороги между Милетополем и современным Балыкесиром. По этой дороге он направился через Каламос к Филадельфии, где жители сначала встретили его дружелюбно, но потом пытались ограбить задние ряды его армии и поплатились за это. Фридрих добрался до Лаодикеи 27 апреля, через тридцать дней после переправы через Дарданеллы. Оттуда он двинулся вглубь страны по дороге, которой следовал Мануил в своем роковом походе к Мириокефалону; и 3 мая после стычки с тюрками миновал поле боя, где еще белели кости погибших. Теперь Фридрих оказался на территории, подвластной сельджукскому султану. Не вызывало сомнений, что Кылыч-Арслан, несмотря на все обещания, не намерен дать крестоносцам мирно пройти по его владениям. Однако величина христианской рати привела его в такой ужас, что он не пытался предпринимать каких-либо серьезных действий, помимо того, что крутился вокруг нее, отлавливая отставших солдат и донимая отряды, отправленные на поиски продовольствия. Тактика сработала эффективно. Голод и жажда вместе с тюркскими стрелами вскоре начали приводить к жертвам среди крестоносцев. Обойдя оконечность гор Султан-Даг и ступив на старинную дорогу, ведущую от Филомелиона на восток, Фридрих 17 мая подошел к Конье. Султан вместе со всем своим двором заблаговременно покинул столицу, и в ходе ожесточенной битвы с сыном султана Кутб ад-Дином император на следующий день сумел пробиться в город. Он не стал надолго задерживаться в его стенах, но все же дал армии немного передохнуть в садах Мерама на его южной окраине. Шесть дней спустя он двинулся в сторону Карамана, куда и прибыл 30-го числа, а оттуда без помех повел армию через перевалы Тавра к южному побережью у Селевкии. В то время этим портовым городом владели армяне, чей католикос поспешил письменно доложить обо всем Саладину. Дорога пролегала по труднопроходимой местности, еды не хватало, а летний зной палил нещадно.