Алексей Комнин пришел в замешательство, узрев толпы крестоносцев: в его войске уже служили латинские наемники, и он был хорошо знаком со строптивостью норманнов и «франков». То, что они хотели захватить Палестину, делало их нашествие несхожим с набегами, с которыми раньше приходилось сталкиваться императору: для него это был неожиданный шанс отбросить турок от Малой Азии и Сирии. Но он боялся, что крестоносцы атакуют Византию, прельстившись ее роскошью: действительно, лотарингцы разграбили город Селимбрию и объявили о намерении штурмовать столицу, когда им прекратили поставку продовольствия. После длительных переговоров (23 декабря 1096 — апрель 1097 гг.) Алексею удалось нанести Готфриду поражение, которое принудило герцога Нижней Лотарингии подчиниться. Сицилийские норманны, самые грозные противники, подошли к тому моменту, как император переправил лотарингцев на азиатское побережье с целью избегнуть опасной концентрации крестоносных войск: но они вели себя необычайно корректно. Провансальцы, выведенные из себя столкновениями на пути, были опасны: они разграбили Роццу, но были потрепаны под Родосто. Проход «французов» произошел без осложнений.
Алексей вознамерился превратить крестоносцев в имперские войска, продемонстрировав, что земли, через которые лежал их путь, хоть и захваченные к тому моменту турками, вовсе не являлись ничейными. Он потребовал от латинян клятву верности и обещания вернуть империи все территории, которые ей ранее принадлежали. Готфрид и все крупные бароны в конце концов принесли клятву, кроме Танкреда и графа Тулузского, который отказался признать Алексея своим господином, по крайней мере, пока тот не вступит в ряды крестоносного воинства; в результате Раймунд всего лишь обещал не причинять никакого вреда Василевсу. Всех, кто принес клятву верности, император осыпал подарками; им выдали плату и обеспечили поставку продовольствия до Анатолии. Правда, Боэмунд стремился добиться большего: он хотел стать вассалом Алексея либо в качестве великого доместика Востока (титул, который принимал командующий византийской армии в Азии), либо в качестве владетеля какого-либо фьефа в Азии — это свидетельствует, что у этого итальянского норманна уже родилась мысль осесть в Леванте. Алексей обещал дать ему фьеф за пределами Антиохии (то есть рядом с Алеппо и Дамаском, землями, которые были завоеваны арабами в VII в. и никогда не возвращались к империи) размером в четырнадцать дней пути на восемь дней, своеобразную мусульманскую марку, которая была бы выгодна византийцам — но это была бы точно такая же марка, как и та, где норманны, приглашенные византийцами, основали итальянское княжество, и, в конце концов, изгнали как мусульман, так и своих византийских союзников…
В сопровождении византийского корпуса под командованием Татикия крестоносцы осадили Никею, столицу сельджукского султаната в Анатолии: 26 июня 1097 г. Никея вновь, более чем на два столетия, стала византийским городом. После первого успеха латиняне направились в малоазиатские степи, где 1 июля все силы анатолийских турок внезапно обрушились на один из двух их отрядов, который возглавляли Боэмунд и Роберт Коротконогий. В критический момент норманнов выручил подоспевший Готфрид Бульонский с остальной армией, и сражение при Дорилее обернулось поражением для турок, чья привычная тактика (обстрел из луков издали) оказалась бесполезной перед все сметающей на своем пути атакой тяжелой кавалерии франков и их стойкостью. Однако франкская кавалерия скоро стала таять: в песках Фригии погибли все лошади с Запада. Турки оставляли после себя «выжженную» землю, и даже взятие франками Конии (Икония, 15 августа 1097 г.) не улучшило ситуации с продовольствием. Трава для лошадей попадалась лишь изредка, и после победы при Гераклее (10 сентября) крестоносное войско разделилось на два корпуса: один под командованием Танкреда и Балдуина Булонского двинулся в Киликию, второй — на север, где занял Цезарею (Кесарию), возвращенную византийцам вместе с Команой (там остался франко-византийский гарнизон во главе с Пьером д'О (d'Aups). После этого отряд спустился до Марата (октябрь 1097 г.) и подошел к Антиохии. В то же время Танкред и Балдуин пребывали в Киликии, где надеялись выгадать для себя помощь армянских вождей. Они выгнали турок, но в конце концов поссорились, и оба покинули регион, в котором Танкред и Гинемер Булонский, действуя в пользу Балдуина, оставили несколько гарнизонов. Сам Балдуин по зову армянских вождей вновь вернулся в Эдессу, где его как родного сына принял владелец города армянин Торос, от которого граф Булонский не замедлил избавиться — или ему в этом помог народный мятеж. Балдуин привел с собой только 80 рыцарей, но вскоре разрозненные воины, из тех, кто ранее потерял коней, постепенно подтянулись к Эдессе, где в конце концов их набралось около двух сотен.