Gdy w 1056 zmarł Henryk III, papież Wiktor II dokonał, z pozoru mało istotnych, zmian administracyjnych. Jedną z nich była zmiana formy graficznej bulli (ołowiana pieczęć urzędu papieskiego z podobiznami świętych Piotra i Pawła), która od tego czasu przedstawiała wizerunek Piotra otrzymującego klucze od Chrystusa, oraz wizerunek Rzymu. Wiktor II zalecił też, by regentką 5-letniego następcy tronu cesarskiego Henryka IV była cesarzowa-wdowa Agnieszka. Gdy więc w dwa lata później Wiktor II zmarł, na jego następcę wybrano – bez udziału rodziny cesarskiej – współpracownika grupy reformatorów Leona IX, Fryderyka z Lotaryngii OSB. Gdy w 1058 grupa pięciu, zebranych poza Rzymem, współpracowników-cardini (kardynałów) wybrała na kolejnego papieża biskupa Florencji Gerharda z Burgundii, formalnie wysłano prośbę o akceptację, do regentki Agnieszki. Nie wiadomo, czy pismo było wysłane przed czy po dokonaniu wyboru. Nowo wybrany Mikołaj II przybył w następnym roku do Rzymu z wojskiem toskańskim oraz grupą reformatorów, by zdetronizować uznawanego za antypapieża-uzurpatora Benedykta X.