Przyjął imię Paschalis II i następnego dnia został konsekrowany przez kardynała biskupa Ostii, Odona.
Sytuacja Paschalisa II na początku pontyfikatu była dość trudna, bowiem wciąż żył antypapież Klemens III, którego popierał cesarz Henryk IV Salicki. Z pomocą Normanów z południa Włoch zdołał jednak usunąć Klemensa III z Rzymu. Antypapież zmarł we wrześniu 1100 roku, a jego dwaj następcy Teodoryk (1100–1101) i Albert (1102) nie zyskali większego poparcia i zostali szybko schwytani i uwięzieni. Nadal jednak trwał konflikt z Henrykiem IV, gdyż Paschalis II ponowił zakaz inwestytury świeckiej, czemu cesarz nie chciał się podporządkować. Dodatkowo w celu wzmocnienia rywalizującej z Cesarstwem Danii usamodzielnił kościół skandynawski tworząc w 1104 arcybiskupstwo w Lund. Wcześniej Kościół w Skandynawii podlegał arcybiskupstwu Bremy.