Уже в Золингене было принято решение о первом римском походе, который должен был принести королю обладание императорской короной. Тогда же в Византию отправилось посольство под руководством Иоанна Филогата, которому было поручено сосватать за будущего императора принцессу самого знатного происхождения. Италии касалось и другое мероприятие символического значения: Оттон уже в Золингене назначил канцлером по делам Италии своего капеллана Хериберта. В лице Хериберта он впервые доверил пост итальянского канцлера немцу — первое указание на то, что он и впредь будет стремиться прочнее подчинить Италию германской власти.
Затем он для начала занялся урегулированием внутригерманских отношений, и поскольку зимой 994–995 годов славяне на границе по Эльбе причиняли заметное беспокойство, Оттон предпринял осенью 995 года военный поход против ободритов, причем на помощь ему пришли польские и богемские войска. Только после этого, весной 996 года, Оттон, побуждаемый призывом о помощи со стороны папы Иоанна XV, выступил в давно запланированный поход через Альпы. Папа, который тем временем был вытеснен из Рима патрицием Кресценцием, страстно ожидал прибытия Оттона, до которого, однако, ему не суждено было дожить. В Павии Оттон получил сообщение, что Иоанн XV внезапно скончался. Это известие было доставлено римским посольством, которое одновременно просило Оттона, как будущего императора, назвать нового папу. В ответ на просьбу Оттон еще в Павии назначил новым папой своего капеллана и двоюродного брата Бруно, сына герцога Оттона Каринтийского и правнука Оттона Великого, и повелел ему через Виллигиза Майнцского и Хильдебальда Вормсского отправляться в Рим. Бруно, назвавший себя папой Григорием V, был первым немцем на папском престоле. Показательно, что Оттон III этим фактом возведения его на престол уже в 996 году отказался считаться с практикой своего деда, возводившего в папы только римлян, желая в лице Бруно поставить во главе римской церкви человека из своего ближнего окружения. Очевидно, что он изначально стремился к тесной связи с папством. Первый торжественный акт нового папы состоял в том, что в день Вознесения, 21 мая 996 года, он короновал своего двоюродного брата Оттона III императорской короной. В силу своего происхождения и положения чужеземца в Риме папе, в свою очередь, приходилось быть заинтересованным в поддержании хороших отношений с императором. Соответственно, оба они направили развитие императорско-папских отношений фактически по новому пути. Симптоматичным было и то, что император и папа вместе провели заседание синода, состоявшееся вскоре после коронации в соборе Святого Петра, и то, что император по этому случаю вместе с понтификом подписал папскую грамоту и большую часть папских постановлений сделал действительными для немецкой церкви, и то, что папа, с другой стороны, фигурировал в императорских постановлениях и вменял в обязанность адресатам папских актов молиться за «honor» («славу») и «potestas» («мощь») императорской власти. Когда Лев Верчеллийский несколькими годами позже воспел своим знаменитым стихом императорско-папское согласие между Григорием и Оттоном, он таким образом восславил именно тот союз, который сложился между императором и папой в 996 году, с назначением Григория V. Правда, сам Оттон не оставлял никаких сомнений в том, что требует для императорской власти руководящей роли в этом союзе, как и вообще с самого начала утверждал свои собственные представления о достоинстве и высшем праве имперской короны. Бросается в глаза, что Оттон III, в отличие от Оттона Великого, не возобновил после своего коронования традиционную имперскую привилегию для римской церкви, известную как «Ottonianum»: очевидно, он уже тогда решил укрепить императорские права в Папской области. Подобно своему отцу, иногда называвшему себя «Romanorum imperator augustus», именовал себя и Оттон III, но теперь уже регулярно, демонстрируя еще и этим свой более выраженный поворот к Риму и римской государственной мысли.
