Тем временем император Исаак снарядил войско под командованием своего племянника Мануила Камиза, опытного командира, закаленного в многочисленных сражениях, и направил его к Филиппополю. Барбаросса послал к Камизу парламентеров, дабы заверить его в мирном характере своих намерений и таким образом избежать столкновения, однако ничего не добился. Когда в конце августа 2000 отборных греческих всадников устроили неподалеку от Филиппополя засаду немецким фуражирам, Фридрих Швабский с 5000 рыцарей атаковал противника и обратил его в бегство. Предводитель этого злосчастного войска, как сообщает византийский источник, возвратился в Константинополь, «словно потерпевший кораблекрушение, нахлебавшийся соленой морской воды».

В преодолении этих преград прошло лето. По расчетам, Фридриху уже давно следовало маршировать в Азии, но вместо этого приходилось готовиться зимовать на европейском берегу, в Филиппополе. Неудачная военная вылазка отрезвляюще подействовала на Исаака, и он освободил людей Барбароссы, в сопровождении своих посланцев отослав их в Филиппополь и велев передать, что согласен на ведение переговоров. Но и на этот раз не удалось прийти к соглашению. Непредвиденная задержка спутала все расчеты Фридриха, причинив ущерб и его репутации овеянного славой императора и полководца, поскольку христианский мир не мог понять, почему крестоносное войско до сих пор не в Азии.

В конце октября освобожденные немецкие послы прибыли в Филиппополь. Вместе с ними опять явился Иоанн Дука в сопровождении высоких придворных чинов. На следующий день Герман Мюнстерский и его спутники доложили собравшимся князьям, рыцарям и клиру о том, как с ними обращались в Константинополе, и о враждебности к крестоносцам, которую там проповедовал с амвона Досифей. Затем впустили греческих послов. Фридрих потребовал полного возмещения ущерба, в первую очередь возвращения отнятых у послов подарков и денег. В весьма сильных выражениях Фридрих бросил Иоанну Дуке упрек в мелочности его господина, в своем послании не пожелавшего признать за ним, императором Фридрихом, титула и имени, известных всему миру. Естественно, Дуке нечего было возразить.

Тем временем и королю Венгрии стало известно о враждебности между Барбароссой и Исааком. Сколь бы дружески он ни был расположен к императору Фридриху, заинтересованность в сотрудничестве с Исааком Ангелом на Балканах брала верх, вынуждая его отозвать венгерский отряд. Фридрих поначалу пребывал в нерешительности, не знал, отпускать венгерских крестоносцев или нет. Наконец, он согласился, ибо «Господь не желает принудительной службы», а сам решил отправиться на зимние квартиры в Адрианополь, куда уже в ноябре прибыла большая часть его войска. Этот город также был оставлен жителями, но не разрушен, так что крестоносцы смогли там устроиться.

Поскольку из Константинополя не поступало никаких вестей, Барбаросса поздней осенью 1189 года всерьез стал подумывать о захвате византийской столицы, не видя иной возможности переправиться в Малую Азию. Эти авантюрные идеи, питавшиеся ненавистью и озлоблением в войске, а также надеждой на большую поживу, уже давно витали в воздухе. В ноябре Фридрих отправил вместе с возвращавшимся домой венгерским отрядом указание королю Генриху VI собрать флот пизанцев и генуэзцев для осады Константинополя, которая должна была начаться в марте. Тогда Барбаросса еще не знал, что в Германии опять разгорелась борьба против Генриха Льва, незаконно вернувшегося на родину.

Попытка получить у Стефана Немани вспомогательный отряд для похода на Константинополь не увенчалась успехом. Зато болгарский князь Петр предложил Фридриху вспомогательное войско в 40 000 болгарских и куманских воинов. Фридрих поблагодарил, однако до заключения соглашения дело не дошло. Из Италии верная императору Пиза ответила, что соберет необходимый флот для блокирования Константинополя с моря. Правда, эта весть поступила лишь в марте, когда конфликт с Византией был урегулирован, и Фридрих перешел Геллеспонт.

Поздней осенью императоры Востока и Запада фактически находились в состоянии войны. Переговоры приостановились, однако Фридрих был готов к их возобновлению. Для него наступление на Константинополь представлялось лишь возможной альтернативой, средством для достижения цели крестового похода, но не самой целью. Исаак, не располагавший достаточными силами для нападения на немецких крестоносцев, также предпочел вступить в переговоры и незадолго перед Рождеством направил к Фридриху своих представителей. По неизвестным нам причинам это посольство оказалось безуспешным. Но уже 21 января в Адрианополе появилось новое посольство, заявившее о готовности василевса дать знатных заложников во исполнение прежде заявленных условий прохождения немцев по византийской территории. Тем самым было выполнено важнейшее требование Фридриха, что позволило начать переговоры. Исаак пошел на уступки. Фридрих благосклонно выслушал послов и направил в Константинополь своих представителей для продолжения переговоров, протекавших неожиданно успешно. К тому времени, очевидно, Исаак понял, в сколь критическое положение он поставил себя, вступив в конфронтацию с крестоносцами.

14 февраля немецкие послы доставили для ратификации договор, полностью отвечавший интересам Фридриха: византийский император отказывался от компенсации ущерба, который могли причинить в его провинциях крестоносцы, а для их переправки на другой берег предоставлял достаточное количество судов; он давал знатных заложников, среди них шесть членов императорской семьи, дабы гарантировать безопасность переправы и дальнейшего движения крестоносцев, которым на всем пути предоставлялось достаточное количество провианта и фуража; за ущерб, причиненный послам Фридриха в Константинополе, выплачивалась компенсация, а все подданные Барбароссы, плененные византийцами с начала конфликта, обретали свободу; договор надлежало подписать патриарху Досифею и в его присутствии клятвенно удостоверить в храме Святой Софии в Константинополе 500 знатным гражданам.

Вскоре затем к Фридриху прибыло посольство от султана Килич Арслана Иконийского, в течение восьми недель удерживавшееся в Константинополе и потерявшее там помимо личного имущества подарки султана. Послы передали заверение своего повелителя, что Фридрих за время прохождения по территории сельджуков может рассчитывать на их поддержку. Спустя некоторое время прибыл и посол Кутбеддина, сына и соправителя Килич Арслана, с аналогичными заверениями.

Заручившись гарантиями безопасности прохождения через Западную Анатолию, Фридрих начал готовиться в путь, велев крестоносцам еще раз принести клятву послушания и верности. 1 марта 1190 года, несмотря на то, что еще стояла холодная и ветреная погода, авангард войска под командованием герцогов Швабии и Баварии выступил в путь. На следующий день двинулся и сам император во главе основной части Христова воинства. Проливные дожди сильно затрудняли продвижение крестоносцев по бездорожью Южной Фракии. Холод, слякоть и недостаток корма вконец измотали лошадей, едва тащивших тяжело нагруженные повозки, часть которых даже пришлось бросить, навьючив груз на верблюдов и мулов.

21 марта крестоносцы наконец-то достигли моря, а на следующий день были в Галлиполи. Здесь все войско опять собралось вместе. Обещанный Исааком транспортный флот был на месте. И опять в авангарде шел герцог Фридрих Швабский, переправившийся с несколькими тысячами рыцарей и лучников на другой берег. Поскольку дождь и ветер усилились, большая часть войска с императором отпраздновала Пасху еще на европейском берегу. Наконец непогода утихла, позволив переправиться и основной части крестоносцев. Последним пересек пролив император, ступивший на азиатский берег под радостное пение труб и ликующие возгласы воинов. Все войско было в сборе, и Фридрих милостиво отпустил византийские корабли, а также большинство заложников. Почти год прошел с того дня, когда крестоносцы покинули Регенсбург, но лишь теперь начиналось самое трудное — беспримерное хождение по мукам.