Религиозные стремления, не так давно обуявшие епископа Пражского, были усилены двумя другими духовными наставниками, Нилом Россанским, который упрекал императора за безжалостность по отношению к Филогатаму, и будущим основателем монашеского ордена, Ромуальдом, которого Оттон сделал своим доверенным лицом и советником. Правитель, убежденный, что Рим стал гнездом порока, был полон решимости его очистить. Дело было срочным, поскольку, никто не знал ни день, ни год наступления страшного суда, а Господь мог прийти неожиданно; горе тому слуге, которого он застал бы спящим! Поэтому следовало действовать быстро, чтобы помешать христианству увязнуть в обыденных заботах. Не был ли это лучший способ возродить его силу, осуществляя великое дело христианизации? Оттон, стремившийся возглавить эту миссию с должным пылом, попытался избавиться от всего греховного в нем самом. Он вновь спустился в подземелье близ монастыря Св. Климента, возможно, бывшего когда-то алтарем Митры. Это место заключало в огромный смысл, в двух шагах от него покоился прах Святого Кирилла, апостола славянского мира, посланного вместе со своим братом Мефодием в эти края басилевсом. Таким образом, миссионерские приемы Византии и сына Феофано оказались поразительно схожи. Он быстро признал самостоятельность церковных структур по отношению к новым христианским объединениям. Он также не касался независимости государств, правители которых приняли крещение. Они вошли в семью христианских государей благодаря связям, которые создавало между ними крестничество: император охотно становился крестным отцом нового крестившегося. Однако такая политика не нравилась немецким прелатам Майнца, Магдебурга и Зальцбурга, которые намеревались подчинить своей власти новые церкви.
Польша первой воспользовалась этой рискованной политикой. Она была союзницей немцев в 984 и 985 гг., когда предательски напала на язычников-лютичей; в 997 г. герцог Болеслав Храбрый выкупил тело Адальберта у его убийц и приказал похоронить в Гнезно.
В самом начале тысячного года Оттон III совершил пешее паломничество, чтобы поклониться могиле своего друга, но его поездка также преследовала папские цели. С согласия папы он превратил Гнезно в архиепископский центр, от которого зависели три викарных епископства — Колобжег, Вроцлав и Варшава. Таким образом, польская Церковь избавилась от германской зависимости. В знак дружеского договора, который его связывал с императором, Болеслав получил копию Святого Копья; на несколько мгновений его увенчали короной Оттона, и он был назван «братом и соратником империи, другом и союзником римского народа». Свободные и верные Церковь и Государство Польши нашли, таким образом, свое место в христианстве. Оттон посетил также Венгрию, чья конница прежде на протяжении полувека внушала животный страх соседним странам. Адальберт смог в течение одной из своих миссионерских поездок подтвердить обращение короля в христианство, сын которого Вайк был окрещен в 994 г. в Кельне в присутствии Оттона III, ставшего его крестным отцом. Вайк, принявший имя Стефана, вступил в бой с противниками христианства. Все так же по воле Сильвестра II в Гране была основана церковная провинция, гарантирующая религиозную самостоятельность Венгрии. В то же самое время император торжественно признал королевскую власть своего крестника, который был коронован 15 августа 1001 г. Как и с Болеславом, отношения Стефана с Оттоном III строились исключительно на их духовной связи. Вдоль далматского берега христианство распространялось под влиянием Венеции, дож которой просил Оттона стать крестным его сына и дочери. Таким образом, сформировалась семья христианских князей; их земли теперь простирались до Вислы, с одной стороны, и до Карпат, с другой. Оттон III сразу стал правителем империи, включающей германцев и итальянцев, от Милана до Рима, и духовным главой всех государств, где соседствовали славяне и мадьяры. В обоих случаях единство не нарушало разнообразия. Для Оттона тысячный год был отмечен не символом страха, а знаком надежды.
Столь живая надежда, как он считал, могла еще больше раздвинуть горизонты его политики. Гордясь тем, что он сумел использовать наследие матери, Оттон считал себя достаточно культурным человеком, чтобы Византия не воспринимала его больше как варвара. Перенял ли он принципы и характер правления императоров Востока? Если бы он попросил руки порфироносной княжны, осмелились бы ему отказать? Возможно, когда-нибудь он заменил бы басилевса, у которого не было наследника мужского пола. Тогда обе части империи, разбитой в былые времена вторжениями, были бы воссоединены, а Рим вновь стал бы «главой мира». Разве не справедливо, что Оттона изобразили на переднем плане, благословляемым рукой Господа, окруженным королями, принимающим клятву верности от Рима, Галлии, Германии и Славии?