Подобное поведение Танкреда не могло понравиться королю Бодуэну, и он решил содействовать возвращению в Антиохию Боэмунда, для чего вместе с патриархом Бернаром начал переговоры с эмиром Данишмендидом о его выкупе.
Когда император Алексей узнал, что его враг Боэмунд попал в плен к туркам, он многократно обращался к эмиру Каппадокии Данишмендиду Малик Гази, требуя выдать его ему. Зная, что нормандец - заклятый враг императора, и опасаясь василевса лично, Малик Гази не торопился выполнять императорские требования и просьбы. Наконец Малик Гази согласился передать Боэмунда императору за значительный выкуп - источники называют сумму в 260 тысяч золотых безантов. Таких больших денег не смог сразу собрать даже император.
Узнав о готовившейся передаче Боэмунда императору, половину выкупа за князя потребовал у Малик Гази иконийский султан Кылыч Арслан как ленный глава всех турок на Анатолийском полуострове. Турецкие князья поссорились. И тут блестящим политиком и дипломатом проявил себя нормандский князь.
Красавец-князь был, благодаря личным связям в гареме эмира и подкупленной страже, в курсе его переговоров и объяснил Данишмендиду, что у императора, после того как он заполучит его, Боэмунда, развяжутся руки, и Алексей первым делом с помощью Кылыч Арслана расправится с ним. Со своей стороны, Боэмунд обещал за себя половину выкупа и военный союз против императора и иконийского султана. В заговор против императора был вовлечен также византийский вельможа, родственник василевса Григорий Таронит, который вел с Малик Гази переговоры о выкупе. После того как король Бодуэн, патриарх Бернар, армянский князь Ког Василий и сторонники Боэмунда в Италии собрали три четверти обещанной суммы, Данишмендид Малик Гази весной 1103 г. выпустил его на свободу. Почти сразу после освобождения нормандца разгорелась длительная война между обманутым Кылыч Арсланом и Данишмендидом, видимо, очень удивленным отсутствием военной помощи от своего «друга» Боэмунда, который предпочел, сидя на заборе, смотреть на драку в соседнем дворе.
Графство Эдесса постоянно находилось под угрозой нападения и не имело естественных границ в виде гор и рек. Поэтому оборона графства, с трех сторон окруженного врагами, строилась при помощи опорных пунктов - укрепленных городов и замков. Жизнь, постоянно проходившая в боевой тревоге, требовала, чтобы начальники гарнизонов были людьми, которым Бодуэн Эдесский мог полностью доверять, и, кроме того, их солдаты должны были быть людьми полу-разбойничьего склада, кому требовалось короткое время на сборы и которых к тому же не слишком обременяла семья. Одновременно Бодуэну нужно было жить в мире с местными христианами, так как латинцев ему недоставало. Первым делом Бодуэн дю Бург, став графом Эдесским, женился на Морфии, младшей дочери армянского князя Гавриила, правителя Мелитены. Он покровительствовал армянской апостольской церкви, и армяне составляли значительную часть его армии. Он дружелюбно относился к сирийцам-яковитам, и с его помощью был даже преодолен раскол яковитской церкви.
Единственный порок, в котором упрекали его хронисты, была жадность, поскольку ему постоянно нужны были деньги. Его рыцари весело рассказывали анекдот о том, как Бодуэн обманул своего тестя Гавриила. Он заявил тестю, что должен своим людям 30 тысяч безантов, и поклялся сбрить бороду, если не достанет денег. Армяне, как и греки, считали бороду обязательной принадлежностью настоящего мужчины, и, представив зятя безбородым, Гавриил пришел в ужас, он дал Бодуэну искомую сумму, предварительно взяв с него клятву, что тот никогда не будет закладывать бороду.
Вскоре Бодуэн II Эдесский получил надежного помощника. Им был прибывший в Эдессу вместе с крестоносцами 1101г. его двоюродный брат (по матерям-сестрам), Жослен де Куртне, младший сын, лишенный наследства. Он получил в лен от Бодуэна II земли на запад от Евфрата с Турбесселем и другими замками. Необыкновенно сильный физически, храбрый и жестокий, он был к тому же еще умным и верным человеком. Он навел ужас на турок к северу от графства, Бодуэн II же совершал набеги на земли к востоку и югу от Эдессы.
В начале 1103 г. эмир Данишмендид Малик Гази напал на Мелитену. Бодуэн не смог или не захотел помочь своему тестю. Гавриил был нелюбим своими подданными за то, что перешел в православную веру. Мелитена была взята турками, а сам Гавриил попал в плен. Один из его замков в горах продолжал оказывать туркам сопротивление. Турки привезли Гавриила к замку, чтобы он приказал замку сдаться. Когда гарнизон отказался, турки зарубили его перед замком.