Маршрут Боэмунда, по-видимому, привел его к Эдессе (Водене), где он вступил на Эгнатиеву дорогу. Оттуда его сопровождал эскорт печенегов с обычными приказами от императора — не давать им грабить окрестности и разбредаться, а также следить за тем, чтобы крестоносцы не оставалась дольше трех дней в одном месте. Основная часть армии без задержки пересекла Вардар, но граф Россиньуоло и его братья с небольшим отрядом задержались на западном берегу. Поэтому печенеги атаковали их, чтобы заставить двигаться вперед. Услышав о бое, Танкред сразу же переправился назад через реку, чтобы прийти им на выручку. Он отбросил печенегов и взял несколько пленных, которых привел перед Боэмундом. Боэмунд допросил их и, услышав, что они выполняли приказ императора, сразу же отпустил. Его политика состояла в том, чтобы вести себя по отношению к императору безупречно.

В своем желании быть безупречным он, скорее всего, отправил послов к императору, еще когда только высадился в Эпире. Когда его армия прошла под стенами Фессалоник и направилась по дороге в Серры, эти послы встретили его, возвращаясь из Константинополя. С ними шел сановник империи, с которым вскоре у Боэмунда завязалась близкая дружба. Его армия не испытывала недостатка в провианте, и взамен Боэмунд обещал не только по возможности не заходить по пути ни в какие города, но и согласился вернуть весь скот, угнанный его людьми. Его соратникам не раз хотелось пограбить страну, но Боэмунд строго-настрого запретил им это.

Армия дошла до Руссы (современный Кешан) во Фракии 1 апреля. Тогда Боэмунд решил поторопиться в Константинополь, чтобы узнать, о чем там ведутся переговоры между императорами и уже прибывшими западными вождями. Он оставил войска под началом Танкреда, который отвел их в плодородную долину в стороне от главной дороги, где они провели Пасху. Боэмунд прибыл в Константинополь 9 апреля. Он расположился за стенами города, у монастыря Космы и Дамиана, а на следующий день был допущен на аудиенцию к императору.

Алексею Боэмунд казался самым опасным из крестоносцев, куда опаснее всех остальных. Прошлый опыт научил византийцев, что нормандцы — грозные враги, честолюбивые, коварные и бессовестные; и Боэмунд в предыдущих кампаниях выказал себя их достойным командиром. Его войска были превосходно организованы, экипированы и дисциплинированы; он пользовался их полным доверием. Как стратег он, вероятно, страдал излишней самоуверенностью и не всегда был осмотрителен, но как дипломат он был убедителен и ловок, а как политик — дальновиден. Внешне он производил сильное впечатление. Анна Комнина, знавшая его и страстно ненавидевшая, не могла не признать его обаяния и восторженно писала о его красивой наружности. Он был невероятно высок и, хотя ему уже было за сорок, обладал фигурой и лицом молодого человека, широкоплечего, с тонкой талией, кожа у него была чиста, а щеки — румяны. Он стриг свои белокурые волосы короче, чем было в обычае у западных рыцарей, и чисто брился. Еще с детства он слегка сутулился, но это не повредило ни его здоровью, ни физической силе. Как говорит Анна, в его лице было что-то жесткое, а в улыбке — зловещее, но так как она, как испокон веку все греки, питала склонность к человеческой красоте, Анна не могла скрыть своего восхищения.

Алексей сперва повидался с Боэмундом наедине, чтобы разузнать его настроения, но, обнаружив, что нормандец настроен весьма дружелюбно и готов идти навстречу, позволил Готфриду и Балдуину, которые все еще гостили у него во дворце, принять участие в беседе. Боэмунд вполне сознательно вел себя столь корректным образом. Он гораздо лучше всех крестоносцев знал, что византийцы до сих пор очень могущественны и что без их помощи ничего не получится. Ссора с ними чревата одними бедами, но разумный человек может извлечь для себя выгоду из союза с ними. Он хотел бы возглавить кампанию, но не имел для этого авторитета папы за своей спиной, и, значит, за главенство ему придется соперничать с другими вождями крестоносцев. Если бы Боэмунд получил официальное назначение от императора, он оказался бы в таком положении, в каком уже мог бы претендовать на руководство. Он смог бы управлять всеми переговорами крестоносцев с императором, он стал бы тем, кому крестоносцам пришлось бы передавать все отвоеванные для империи земли. Он был бы стержнем, на котором вращался бы весь христианский альянс. Он без малейших колебаний поклялся в верности императору и затем предложил свою кандидатуру на пост великого доместика Востока, то есть главнокомандующего всеми императорскими силами в Азии.

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

Затем армию Боэмунда вызвали в Константинополь и 26 апреля переправили через Босфор к армии Готфрида у Пелеканона. Танкред, который не понимал и не принимал дядиной политики, прошел через город ночью вместе с двоюродным братом Ричардом Салернским, лишь бы не приносить присяги. В тот же день граф Раймунд Тулузский прибыл в Константинополь и был принят императором.

Раймунд IV, граф Тулузский, больше известный как граф Сен-Жильский по названию своего прежнего владения, был уже человеком зрелого возраста, вероятно приближался к шестидесятилетию. Его родовое графство было одним из богатейших во Франции, а недавно он унаследовал еще и не менее богатое маркизство Прованс. Через брак с принцессой Эльвирой Арагонской он был связан с королевскими домами Испании и принял участие в нескольких религиозных войнах с испанскими мусульманами. Он был единственным крупным аристократом, с которым папа Урбан лично обсуждал свой проект Крестового похода, а также первым, кто объявил о своем участии в нем. Поэтому он не без оснований считал, что имеет право быть его светским руководителем. Но папа, который желал удержать движение под своим духовным контролем, так и не признал его притязаний. Раймунд, скорее всего, надеялся, что рано или поздно необходимость в светском командующем станет очевидной. А между тем он планировал отправиться на Восток в обществе его духовного руководителя — епископа Пюиского.

Раймунд возложил на себя крест еще во время Клермонского собора, в ноябре 1095 года, но лишь к следующему октябрю закончил подготовку к отъезду. Он принес обет провести остаток своих дней в Святой земле; но возможно, что этот обет он принес с некоторыми оговорками, ибо, оставляя свои земли во Франции на попечение своему незаконнорожденному сыну Бертрану, граф ничем не показал, что отрекается от своих прав. Вместе с ним должны были отправиться его жена и их законный сын Альфонсо. Раймунд продал или заложил часть своих земель, чтобы собрать средства на экспедицию, но, видимо, отчасти сэкономил на экипировке. Трудно сказал, что это был за человек. Судя по поступкам, он отличался тщеславием, упрямством и в какой-то мере алчностью. Однако его любезные манеры произвели впечатление на византийцев, которые нашли его куда более цивилизованным, нежели его соотечественники. Он также показался им более надежным и честным. Анна Комнина, которую последующие события настроили в его пользу, хвалила его превосходный характер и чистую жизнь. Адемар Пюиский, который, безусловно, был человеком высоких нравственных стандартов, явно считал его достойным другом.