В это время Боэмунду II, сыну основателя княжества Антиохия, исполнилось 18 лет. Он передал своему двоюродному дяде, великому графу Сицилийскому Рожеру II, свои владения в Италии и в сентябре 1126 г. с некоторым количеством воинов и лошадей на 24 кораблях прибыл в Сен-Симеон. В Антиохии его торжественно встречал Бодуэн. Боэмунд был таким же богатырем и светловолосым красавцем, как отец, и получил хорошее воспитание и образование у матери, Констанции Французской. С королем Бодуэном II в Антиохию прибыла его вторая, 16-летняя дочь Алиса, и, согласно заключенному договору, молодые вступили в брак. Теперь Бодуэн мог уделить больше внимания своему королевству. Молодой муж сразу же отправился воевать. Он отвоевал у эмира Хомса Кафартаб и проявил отвагу в столкновениях с войсками эмира Шайзара.
В начале 1128 г. умер верный друг и помощник короля патриарх Гормон. Его преемником стал знатный француз и родственник короля, аббат из Шартра Этьен де Ла Ферте. Он не оправдал надежды короля Бодуэна на дружеское и родственное сотрудничество. Этьен немедленно напомнил королю о договоре между Готфридом и Даимбертом, по которому Яффа должна быть передана патриарху, так же как и Иерусалим после завоевания Аскалона. Король не стал даже разговаривать с ним об этом, и их отношения сразу испортились. Их отношения продолжали ухудшаться, однако патриарх был слишком крупной фигурой, и король не знал, как выйти из этого положения. На счастье короля, патриарх после короткой болезни умер в начале 1130 г. Его сторонники подозревали отравление. Когда король пришел к патриарху, чтобы справиться о здоровье, тот ответил: «Со мной все так, как Вы того желаете». Его преемником был выбран приор церкви Гроба Господня Гийом из Мессины, человек добрый, благочестивый, простодушный и необразованный. Он во всем и всегда был согласен с королем и был им любим и почитаем.
Одной из главных задач, стоявших перед королем, было определиться с престолонаследием. У Бодуэна II не было сыновей, только четыре дочери — Мелизанда, Алиса, Годиерна и Ивета. Наследницей трона в браке с подходящим мужем назначили старшую дочь Мелизанду. Это означало замену мужского порядка наследования (агнат), при котором наследниками мужчин являются их кровные родственники мужчины, смешанным порядком наследования (когнат), при котором наследуют все кровные родственники, включая дочерей. Эта замена явилась прецедентом, которому впоследствии часто следовали. Теперь нужно было найти мужа для Мелизанды, который выполнял бы королевские воинские обязанности, вместе с ней правил и позаботился о наследнике трона.
Осенью 1127 г., утвердив решение на Коронном совете, Бодуэн послал Гийома де Бюра, князя Галилеи и коннетабля королевства, и Ги Брисбара, сеньора Бейрута, во Францию просить короля Людовика VI порекомендовать подходящего человека из французской знати в мужья принцессе. Людовик VI рекомендовал овдовевшего графа Фулька V Анжуйского. Фульк был главой одного из самых богатейших и сильнейших графств во Франции и на протяжении многих лет союзником короля Франции в его борьбе с государством Генриха I, сына Вильгельма Завоевателя, объединившего королевство Англию с герцогством Нормандия. Граф требовал у Генриха I передачи ему для сына графства Мэн, на которое он получил право, женившись на его наследнице, теперь уже покойной.
Чтобы лишить Францию могущественного союзника, Генрих I предложил графу женить его сына и наследника Жофруа на своей дочери и наследнице, бездетной вдове германского императора Генриха V Матильде. После того как в январе 1127 г. Матильда была официально провозглашена наследницей Англии и Нормандии, оба графа — отец и сын — дали согласие, несмотря на то что невеста была на 11 лет старше 14-летнего жениха: приданое того стоило. Граф Фульк отошел от военного союза с Людовиком VI, но остался его другом. Теперь граф решил оставить наследственные земли своему сыну и отправиться на Восток. Фульк уже был в 1120 г. паломником в Святой Земле и познакомился с Бодуэном и, возможно, с Мелизандой. С кандидатурой Фулька в качестве наследника престола согласились и Бодуэн, и папа Гонорий II.
Чтобы сделать для графа женитьбу более привлекательной, с Фульком подписали договор, что он станет королем, а не принцем-консортом (супругом), и вместе с женой будет править государством. Освоивший во время подготовки бракосочетания сына брачно-юридические тонкости Фульк выдвинул два дополнительных условия: во-первых, папа должен официально подтвердить законность избрания Бодуэна II королем; во-вторых, Иерусалим должен официально провозгласить Мелизанду наследницей. Оба условия были выполнены, и Фульк дал свое согласие на брак. Бодуэн и сам не менее графа был заинтересован в том, чтобы никто не сомневался в законности престолонаследия его самого, его дочери и Фулька.