Так и не сбылось намерение Барбароссы совершить поход против Сицилии, опираясь на силы ломбардских городов (прибывшее из Германии ополчение было малочисленно). Более того, слишком жесткие и решительные действия Райнальда изменили настроение в Северной Италии не в пользу императора. Если поначалу здесь радовались, что освободились от тирании Милана, то вскоре застонали под гнетом новых податей и заговорили о тирании императорских подеста. Эти корыстные и жестокие люди вели себя скорее как оккупационные власти, нежели уполномоченные управляющие в равноправной части Империи. И ответная реакция не заставила себя долго ждать. Стало очевидно, что без сильного немецкого войска здесь не удержать власть. Когда не увенчалась успехом и попытка исправить положение с помощью политических мер, Барбаросса решил вернуться в Германию. Выраженное за три года до того оптимистическое мнение одного из приближенных императора: «Одержав верх над Миланом, мы окончательно победили», не оправдалось.
Еще раньше, до того, как начались беспорядки в Вероне, отправился на родину Райнальд Дассельский. Хотя в Кельне у него и были надежные люди, от его имени управлявшие архиепископством, однако на кельнский соборный капитул в целом нельзя было положиться. Духовенство почти не скрывало своей неприязни к человеку, по приказу императора назначенному архиепископом. Кроме того, Кельнское архиепископство находилось в весьма тесных отношениях с церквами Англии, поэтому именно здесь знаменитый Иоанн Солсберийский, убежденный сторонник Александра III, развернул свою агитацию против Райнальда как «злейшего врага церкви, в своем безрассудном шутовстве назвавшего суверенных государей Франции и Англии малыми королями провинций».
Тем важнее было для Райнальда прибыть триумфатором и не с пустыми руками. Так, еще из Италии он написал клиру и гражданам Кельна, что возвращается домой с великими дарами, «кои ни с чем на свете нельзя сравнить, — со святыми мощами Трех Мудрецов и Царей, до сих пор покоившимися в Милане». Это сокровище сулило прославить Кельн, привлечь к нему паломников со всего христианского мира. Доставка этих бесценных мощей была сопряжена с почти непреодолимыми трудностями. Мало того, что пфальцграф Рейнский и ландграф Тюрингский, непримиримые враги Райнальда, не намерены были упускать замечательную возможность завладеть ими, так еще и Александр III написал одному из своих друзей в Реймс, что тот может славно услужить Царю Небесному, если схватит «императорского канцлера Райнальда, главного зачинщика церковных смут», которому придется ехать в Германию через Фландрию, поскольку другие пути для него закрыты.
Однако Райнальд сумел обмануть своих врагов. Сначала он отправился в Бургундию, дабы проверить надежность пограничных укреплений и добиться признания в тех краях Пасхалия III. Последнее оказалось невыполнимым, поскольку никто и слышать не хотел о новом императорском папе. Если Виктора все же, хотя и неохотно, признавали, учитывая принятые собором решения, то разыгранную в Лукке комедию все единодушно отвергали. Многие даже проклинали нового императорского ставленника, открыто называя его архиеретиком. И даже верный друг, новый вассал императора, Генрих де Труа уклонился от беседы, срочно уехав в Париж, чтобы посовещаться с королем Людовиком VII.
Желая создать у поджидавших его врагов ложное впечатление, будто он собирается еще долго пробыть в Бургундии, Райнальд принялся обследовать крепостные сооружения, давая указания, где и что исправить, и напоминая при этом, что лично проверит исполнение. Все думали, что он еще несколько недель пробудет в Бургундии, тогда как и след его там уже простыл. С тяжелыми мраморными саркофагами он продвигался укромными путями на север. Там, где ему удавалось остаться неузнанным, он выдавал себя и своих спутников за сопровождение, обязанное доставить на родину тела павших в Италии немецких господ. Там, где была угроза преследования, он отсиживался днем в укрытии, передвигаясь только по ночам и приказав перековать подковы лошадям задом наперед. К этой хитрости, по древнесаксонским преданиям, прибегал еще герцог Видукинд, сражавшийся за свободу родной Саксонии, когда за ним шел по пятам Карл Великий. Так Райнальду удалось прибыть 23 июля 1164 года в Кельн, обитатели которого устроили ему восторженный прием. Благодарные граждане Кельна решили изготовить для своей вновь обретенной святыни великолепный ковчег, и поныне служащий украшением Кельнского собора, дабы святые мощи получили достойное место упокоения.
В Германии тогда было неспокойно. Помимо давней вражды Райнальда Дассельского с пфальцграфом Рейнским и ландграфом Тюрингским, в Швабии возник крупный конфликт между Вельфом VI и пфальцграфом Тюбингенским Гуго. Под командованием Вельфа в сентябре 1164 года большое войско подступило к Тюбингенскому бургу, в котором, ввиду подавляющего превосходства противника, сочли за благо перейти к переговорам. Однако безрассудство и самонадеянность отдельных вельфских рыцарей позволили осажденным не только обратить в бегство войско Вельфа, но и захватить около 900 пленников и богатую добычу. Слава об этой победе жила столь долго, что и спустя десятилетия вдохновила великого миннезингера Вольфрама фон Эшенбаха, воспевшего и окончательно обессмертившего ее в рыцарском романе «Парцифаль». Император знал о феодальных усобицах на родине, поэтому сразу же по прибытии 1 ноября 1164 года из Италии в Ульм назначил на середину месяца рейхстаг в Бамберге. Там ему удалось добиться от пфальцграфа Тюбингенского освобождения пленников, а мстительные Вельфы пообещали соблюдать в течение года перемирие. Был улажен и раздор между архиепископом Кельнским и пфальцграфом Рейнским.
После бамбергского рейхстага император поскакал на Рейн и некоторое время пробыл в Эльзасе, где пожаловал статус города местечку Хагенау, в котором располагался бург его отца. Еще в первые годы своего правления Фридрих велел обновить и расширить это родовое гнездо. До конца года он успел побывать в Страсбурге, где провел хофтаг, а в начале февраля 1165 года встретился в Госларе с архиепископами Майнцским и Кельнским и некоторыми другими князьями церкви. Гослар относился к Майнцской епархии, архиепископ которой недавно, совершая паломничество к святым местам во Франции, принес присягу на верность папе Александру III. И тем не менее он продолжал признавать отлученного от церкви императора как своего государя. Правда, легату папы Пасхалия он пригрозил вырвать глаза, если тот еще хоть раз появится на территории Майнцской епархии. Противостояние сторонников и противников Александра в последние месяцы еще более ожесточилось. Число тех, кто поддерживал враждебного императору папу, пополнили также архиепископы Магдебургский и Трирский.
Сам же император в это время обдумывал планы коренного изменения политической обстановки на Западе в свою пользу. Для этого требовалось взаимодействие с королями Англии и Франции. Готовясь к реализации этого плана, Фридрих часто встречался с духовными и светскими князьями своей Империи. Райнальд Дассельский получил задание отправиться ко двору английского короля, дабы сделать ему весьма заманчивое предложение о заключении династического брака. На этом должно было зиждиться сотрудничество в области церковной политики, к которому предполагалось подключить и короля Франции. Конечной целью виделась ликвидация схизмы — разумеется, при условии устранения Александра III. Говорили, что если все получится, как было задумано, то император в качестве государя-миротворца и главы христианского мира поведет новое крестоносное войско освобождать Святую землю и живущих в ней христиан от притеснений со стороны сельджуков.
Делегацию от императора в апреле 1165 года радушно встретил в Руане король Англии. Правда, английский клир, поддерживавший Александра III, не хотел иметь ничего общего с отлученным от церкви германским канцлером, однако Генрих II был рад предложению обручить свою старшую дочь, девятилетнюю Матильду, с богатейшим немецким князем, Генрихом Львом. Еще более лестным показалось ему предложение императора отдать его младшую дочь в жены своему сыну Фридриху. Генрих II согласился на эти предложения, что предвещало успешное выполнение Райнальдом своего следующего задания. Без особого труда ему удалось вовлечь английского короля в союз против Александра III, к сторонникам которого в Англии тот относился резко неприязненно. Договорились, что два представителя Генриха II отправятся вместе с немецкой делегацией на рейхстаг в Вюрцбург, дабы там клятвенно подтвердить достигнутое соглашение. Кроме того, Генрих II обещал встретиться осенью 1165 года с императором, а затем добиться от английских епископов присяги на верность папе Пасхалию III. Достигнутый Райнальдом успех превзошел все ожидания.