В свою очередь святой престол стремился к переговорам, чтобы заручиться помощью Штауфена для восстановления своей власти в Риме. Поэтому первые приглашения на переговоры поступили от него, и в конце концов были услышаны после заключения мирного договора в Констанце. Но по прибытии в Верону для встречи с Фридрихом Луцию III пришлось ждать его несколько недель, потому что монарх продолжал свою деятельность и обсуждения, крайне важные для реализации его программ.
По его приказу агенты развернули деятельность по обеспечению ему эффективного контроля над альпийскими перевалами и дорогами, ведущими с высокогорных плато в равнину По. Сам Фридрих с 1178 года принял необходимые подобные же меры в Пьемонте, а его представители и доверенные лица дополняли и распространяли их на области поблизости от озер Комо Гарда. Вновь взимались дорожные пошлины, укреплялись замки, расставлялись маленькие гарнизоны, жаловались сеньории и поместья (самой знаменательной из этих инвеститур стало пожалование в октябре 1184 года Опизо д’Эсте земель и прерогатив, которыми Генрих Лев владел неподалеку от Милана и в Лигурии).
Эта политика, включающая одновременно восстановление наследственных поместий и ленных владений, после соглашения в Констанце сопровождалась тайными переговорами с Миланом. Фридрих понял, что этот город является самой влиятельной среди ломбардских коммун и единственной из них, достаточно богатой и динамичной для того, чтобы иметь широкие взгляды в дипломатии и возбуждать дружеское расположение либо протесты. Он также знал, что Милан надежнее, чем какой-либо другой город, защищает доступ к главным альпийским дорогам. Поэтому с ним лучше договориться, чем иметь своим противником. Таким образом, новые методы вели к полному перевороту в его союзных связях в Северной Италии.
На юге полуострова императору также пришлось полностью пересмотреть свою тактику. Уже в 1173 году он попытался сблизиться с королевским двором в Палермо, обеспокоенным амбициями Мануила Комнина в центральном Средиземноморье. Попытка не удалась из-за раскола и приверженности Сицилии Александру III. Тем не менее эта обеспокоенность нормандской монархии облегчила заключение перемирия в Венеции, а с 1177 года отношения между королевскими дворами были добросердечными.
Видимо, в связи с обсуждениями в Констанце контакты их стали более тесными, хотя мы ничего об этих отношениях не знаем. Во всяком случае, они привели к общему соглашению без детальных уточнений, без составления мирного договора, так как фактически между обоими правительствами не было разногласий. Просто в ходе переговоров Фридрих признал легитимность нормандской династии и предложил ей свою моральную поддержку против византийских амбиций. Но, по тогдашнему обыкновению, чтобы публично продемонстрировать новое согласие, было решено, что сын императора Генрих VI, король римлян, женится на тетке юного короля Вильгельма II Констанции, дочери Роджера II. Помолвка была официально объявлена 29 октября в Аугсбурге. Для Штауфена это стало явным успехом и возможностью для его сына в дальнейшем осуществлять более действенный контроль над Южной Италией. Однако сицилийский брак еще не обеспечивал наследования трона. Историки неоднократно слишком легко приписывали Фридриху этот гениальный ход, потому что позже Генрих VI стал королем Сицилии. Но в 1184 году Вильгельм II был молодым человеком, всего лишь три года назад женившимся на очень юной женщине, и ничто не предвещало того, что их союз останется бездетным. Зато помолвка тетки, ближайшей его родственницы, ввиду того, что детей у него не было, изолировала папскую власть в дипломатическом отношении. И все же представляется невероятным, чтобы все это было обговорено и решено без ведома Луция, потому что секрет такого порядка не мог быть полным, его должны были доверить, по крайней мере, архиепископу Палермо, который не мог не известить об этом папу. Кроме того, папа являлся сюзереном королевства: юридически трудно было заключить брак без его разрешения, так как невеста в тот момент была наследницей трона.
И все же очевидно, что папа, поставленный в известность, должен был попытаться помешать этому союзу. Если явно он этого не сделал, то лишь потому, что Фридрих очень ловко использовал некоторые аргументы. Он сумел сыграть на антивизантийских настроениях главы римской церкви, который глубоко переживал события в святой земле. Он сожалел об антиевропейских происках жителей Востока (в 1182 году во время анархии, наступившей после смерти Мануила Комнина в 1180 году, европейцы стали жертвами кровавой бойни), и, по примеру высшего духовенства или знати Иерусалимского королевства, считал василевса ответственным за успехи ислама. Он предстал как принц, обеспокоенный ситуацией в святых местах и готовый повсеместно подчеркивать несостоятельность греков, обуздывая одновременно их выступления против королевского двора в Палермо. В это же время он беспрестанно заявлял, что более чем когда-либо полон решимости помогать святому престолу, что и доказал, сославшись на встречу с Луцием III.