Однако этих мер в пользу церкви оказалось недостаточно, чтобы освободить душу юного императора от тяжкого бремени: его угнетало, что он действует больше под натиском обстоятельств и под влиянием своих советников, нежели по собственному побуждению. Вспоминались слова святого Адальберта о бренности всего земного и о долге государя думать о вечном. Сколько часов было проведено в беседах с этим необыкновенным человеком, до того как он отправился к язычникам-пруссам, полный решимости принять смерть мученика за веру! Гибель Адальберта в апреле 997 года до глубины души потрясла Оттона III. Он добился, чтобы сего великомученика Христова незамедлительно причислили к лику святых, и учредил в Ахене монастырь в его честь, надеясь, что там упокоятся и мощи новоявленного святого. Однако польский князь Болеслав Храбрый упредил императора, на вес золота выкупив у пруссов тело Адальберта и велев похоронить его в Гнезно, собственной резиденции, возвысив тем самым ее значение и сделав ее местом паломничества.
И Оттон III, завершив неотложные дела, решил почтить память своего друга, стяжавшего бессмертную славу, пройдя паломником по местам, где некогда ступала его нога. После краткого пребывания в Риме он в начале 999 года отправился к святыням архангела Михаила на Монте-Гаргано. Не с императорской пышностью, а пешком двинулся он в путь, посетив заодно и святые места на Монте-Кассино, где Бенедиктом Нурсийским в 529 году был учрежден первый бенедиктинский монастырь. Своим покаянным паломничеством Оттон III немало удивил не только немцев из собственного окружения, но и встречавших его жителей лангобардских княжеств, впервые видевших императора. Хотя его поступок и находился в полном согласии с идейными течениями и аскетическими настроениями того времени, однако казалось диковинным подобное смирение носителя высшей светской власти.
Правда, дело не обошлось без трагикомического происшествия с легким детективным налетом. На обратном пути Оттон III попросил у жителей Беневента драгоценную реликвию, коей те располагали — мощи апостола Варфоломея, дабы поместить их в Риме в церкви, которую он собирался построить в честь Адальберта. Беневентцы оказались в большом затруднении, не решаясь отказать в просьбе императору, но и не желая лишиться своего величайшего сокровища. Выход из щекотливого положения нашли в благочестивом обмане: посоветовавшись со своим архиепископом, они отдали вместо мощей святого Варфоломея менее дорогую святыню — мощи Павлина Ноланского, погребенного в их кафедральном соборе.
Обман открылся позднее, а пока император продолжил паломничество, в ходе которого посетил и отшельника Нила, обиженным удалившегося из Рима после расправы над Иоанном Филагатом. Почтенный старец радушно принял в своей убогой хижине близ Гаэты Оттона III, мучимого угрызениями совести и обещавшего исполнить любое его желание. Нил ни о чем не просил, сказав, что будет молиться о спасении души Его Величества. Растроганный до слез император получил благословение святого, однако так и не смог уговорить его перебраться в Рим.
Паломничество Оттона III в Южную Италию имело и политическое значение. Поскольку Монте-Гаргано находится в Апулии, на территории, подвластной Византии, Оттон III мог использовать свое пребывание здесь для ознакомления с политической обстановкой. Хотя экспансия Империи в Южной Италии после смерти Оттона II временно прекратилась, передвижение императора без сопровождения войска показало, что господство немцев, в то время не слишком обременительное, в лангобардских княжествах признавалось по крайней мере номинально.
Тем временем в Риме произошли важные перемены. Еще находясь в Южной Италии, Оттон III узнал о смерти своего кузена, папы Григория V, наступившей в феврале или марте 999 года на двадцать седьмом году жизни. Возвратившись в марте в Рим, император обеспечил избрание его преемником своего учителя и советника Герберта. И на сей раз процедура избрания, если оно вообще проводилось, была простой формальностью. В начале апреля новый папа, не встречая каких-либо возражений, был рукоположен и принял имя Сильвестра II. Тесная связь между папством и Империей, нашедшая свое выражение в назначении Герберта, лучше всего символизировалась выбором этого имени: Сильвестр I был папой при императоре Константине Великом, и теперь Оттону III надлежало стать новым Константином при папе Сильвестре II, восстанавливая единство христианского мира в рамках возрожденной Римской империи, сила которой заключалась в единении обеих универсальных властей — светской и духовной, императора и папы.