Попытка получить у Стефана Немани вспомогательный отряд для похода на Константинополь не увенчалась успехом. Зато болгарский князь Петр предложил Фридриху вспомогательное войско в 40 000 болгарских и куманских воинов. Фридрих поблагодарил, однако до заключения соглашения дело не дошло. Из Италии верная императору Пиза ответила, что соберет необходимый флот для блокирования Константинополя с моря. Правда, эта весть поступила лишь в марте, когда конфликт с Византией был урегулирован, и Фридрих перешел Геллеспонт.
Поздней осенью императоры Востока и Запада фактически находились в состоянии войны. Переговоры приостановились, однако Фридрих был готов к их возобновлению. Для него наступление на Константинополь представлялось лишь возможной альтернативой, средством для достижения цели крестового похода, но не самой целью. Исаак, не располагавший достаточными силами для нападения на немецких крестоносцев, также предпочел вступить в переговоры и незадолго перед Рождеством направил к Фридриху своих представителей. По неизвестным нам причинам это посольство оказалось безуспешным. Но уже 21 января в Адрианополе появилось новое посольство, заявившее о готовности василевса дать знатных заложников во исполнение прежде заявленных условий прохождения немцев по византийской территории. Тем самым было выполнено важнейшее требование Фридриха, что позволило начать переговоры. Исаак пошел на уступки. Фридрих благосклонно выслушал послов и направил в Константинополь своих представителей для продолжения переговоров, протекавших неожиданно успешно. К тому времени, очевидно, Исаак понял, в сколь критическое положение он поставил себя, вступив в конфронтацию с крестоносцами.
14 февраля немецкие послы доставили для ратификации договор, полностью отвечавший интересам Фридриха: византийский император отказывался от компенсации ущерба, который могли причинить в его провинциях крестоносцы, а для их переправки на другой берег предоставлял достаточное количество судов; он давал знатных заложников, среди них шесть членов императорской семьи, дабы гарантировать безопасность переправы и дальнейшего движения крестоносцев, которым на всем пути предоставлялось достаточное количество провианта и фуража; за ущерб, причиненный послам Фридриха в Константинополе, выплачивалась компенсация, а все подданные Барбароссы, плененные византийцами с начала конфликта, обретали свободу; договор надлежало подписать патриарху Досифею и в его присутствии клятвенно удостоверить в храме Святой Софии в Константинополе 500 знатным гражданам.
Вскоре затем к Фридриху прибыло посольство от султана Килич Арслана Иконийского, в течение восьми недель удерживавшееся в Константинополе и потерявшее там помимо личного имущества подарки султана. Послы передали заверение своего повелителя, что Фридрих за время прохождения по территории сельджуков может рассчитывать на их поддержку. Спустя некоторое время прибыл и посол Кутбеддина, сына и соправителя Килич Арслана, с аналогичными заверениями.
Заручившись гарантиями безопасности прохождения через Западную Анатолию, Фридрих начал готовиться в путь, велев крестоносцам еще раз принести клятву послушания и верности. 1 марта 1190 года, несмотря на то, что еще стояла холодная и ветреная погода, авангард войска под командованием герцогов Швабии и Баварии выступил в путь. На следующий день двинулся и сам император во главе основной части Христова воинства. Проливные дожди сильно затрудняли продвижение крестоносцев по бездорожью Южной Фракии. Холод, слякоть и недостаток корма вконец измотали лошадей, едва тащивших тяжело нагруженные повозки, часть которых даже пришлось бросить, навьючив груз на верблюдов и мулов.
21 марта крестоносцы наконец-то достигли моря, а на следующий день были в Галлиполи. Здесь все войско опять собралось вместе. Обещанный Исааком транспортный флот был на месте. И опять в авангарде шел герцог Фридрих Швабский, переправившийся с несколькими тысячами рыцарей и лучников на другой берег. Поскольку дождь и ветер усилились, большая часть войска с императором отпраздновала Пасху еще на европейском берегу. Наконец непогода утихла, позволив переправиться и основной части крестоносцев. Последним пересек пролив император, ступивший на азиатский берег под радостное пение труб и ликующие возгласы воинов. Все войско было в сборе, и Фридрих милостиво отпустил византийские корабли, а также большинство заложников. Почти год прошел с того дня, когда крестоносцы покинули Регенсбург, но лишь теперь начиналось самое трудное — беспримерное хождение по мукам.