Чтобы обуздывать римских баронов, надо было иметь под рукой проворных союзников. Гильдебранд отправился вес ти переговоры с норманнами; они обязались защищать папу. В феврале они уже ведут борьбу с приверженцами Бене дикта X. В июне Николай II отправляется на юг Италии; он сзывает собор в Мельфи, уступает Роберту Гюискару, вместе с титулом герцога Калабрии, Апулию и, условно, Сицилию; взамен этого Роберт клянется быть верным союзником Римской церкви.
Не пора ли было изменить систему папских выборов, недостатки которой обнаружились теперь лишний раз, и решительной реформой предупредить беспрестанно возобновляющиеся смуты? В апреле 1059 г. на соборе в Риме Николай II обнародовал знаменитый декрет, который в основе изменил организацию папства:
«Вооружившись авторитетом наших предшественников и других святых отцов, мы приказываем и постановляем, чтобы, в случае смерти первосвященника Римской церкви, кардиналы-епископы предварительно обсудили с величайшим вниманием вопрос о выборе, потом привлекли к совещанию кардиналов-священников и затем спросили у остального духовен ства и народа согласия на новое избрание; чтобы предупредить всякую попытку к подкупу, пусть производят избрание церковнослужители, а остальные следуют за ними. Если церковь (Римская) предлагает кого-нибудь, обладающего необходимыми качествами, пусть его выберут; если нет, пусть возьмут его из другой церкви. Почет и уважение, следуемые сыну нашему королю Генриху, те перь королю, а в будущем, если будет на то воля Божья, императору, да будут сохранены, как мы уже обещали ему, точно так же и его преемникам, которые лично получат этот сан от апостольского престола. Если злоба нечести вых и дурных людей будет настолько сильна, что окажется невозможным приступить в Рим к непорочному, правди вому и свободному от симонии избранию, пусть кардиналы-епископы присоединят к себе священство и светских католиков, хотя бы в небольшом числе, и пусть они имеют право, в согласии с Царем непобедимым, выбрать перво священника апостольского престола в том месте, где то покажется им наиболее удобным. Вечная анафема и отлу чение дерзкому, который не послушается нашего указа и в самонадеянности своей будет пытаться поработить и сму тить церковь Римскую! Да испытает он в этой жизни и жизни будущей гнев всемогущего Бога и ярость апосто лов Петра и Павла, церковь которых он хотел погубить! Да будет дом его пуст, да сделаются его дети сиротами, его жена вдовой, да будут изгнаны он и его сыновья, да будут они принуждены выпрашивать свой хлеб и лишены жилища! Пусть лихоимец изведет себя над своим добром, да будет разграблен плод его трудов, да восстанет на него вся земля, да будут ему враждебны все стихии».