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