Die folgende Phase war stärker von diplomatischen Schritten geprägt, Friedrich II. unternahm keine militärischen Aktionen gegen die Stadt Rom mehr. Die Papstwahl stand unter ungünstigen Bedingungen: zwei Kardinäle waren in apulischer Gefangenschaft, einr (Johann von Colonna) befand sich im Lager des Kaisers. Die 11 übrigen mußten mit 2/3 Mehrheit einen neuen Papst wählen. Innerhalb dieser Gruppe gab es eine stärkere Friedens- und eine schwächere Kriegspartei, längere Verhandlungen waren wahrscheinlich. Der Herrscher von Rom zu dieser Zeit, Senator Matthäus Orsini fürchtete bei längerer Sedisvakanz um die Sicherheit der Stadt, weil er einen neuen Angriff des in der Nähe stehenden kaiserlichen Heeres erwartete (was tatsächlich nicht Friedrich II. Plänen entsprach).
Um die Kardinäle zu einer raschen Wahl zu drängen, schloß er sie unter menschenunwürdigen Bedingungen im Septizonium Severus, einem verfallenen Palast des Kaisers Severus, ein. Dieses erste (und unfreiwillige) Konklave der Kirchengeschichte begründete später eine entsprechende Tradition. Während der zweimonatigen (!) Beratungen starb ein Kardinal, zwei weitere erkrankten tödlich. Einer von ihnen war der neue Papst Cölestin IV., der am 17. Tag seines Pontifikats noch vor der Weihe starb. Mit einer erneuten Papstwahl drohte auch wieder ein Konklave, so daß vier Kardinäle aus Rom nach Annagni flohen. Die räumliche Zersplitterung des gesamten Kollegiums verzögerte die Wahl weiter, Erst am 25. Juni 1243 wurde in Annagni der Kardinal Sinibald Fiesco aus Genua zum Papst Innozenz IV. gewählt. Friedrich II. begrüßte diese Wahl, denn der neue Papst war eng mit den Ghibellinen, seinen italienischen Anhängern verwandt, war ein Mitglied der Friedenspartei, ein bedeutender Kanonist und urbaner Charakter. Ihm fehlte der Fanatismus seines Vorgängers, auch wenn er - was dme Kaiser hätte auffallen müssen - mit seinem Namen an den großen, streitbaren Innozenz III. anknüpfte.
Erste Verhandlungen mit Innozenz IV. waren durchaus erfolgreich: Thaddäus von Suessa, Petrus de Vinea und Berath von Palermo konnten als kaiserliche Vermittler die Atmosphäre entspannen. Strittig blieb die Lombardenfrage, die Friedrich II. trotz seiner Bereitschaft zu Unterwerfung und Kirchenbuße aus dem Friedensschluß heraushalten wollte, weil der Bann nicht wegen dieses Problems erfolgt sei. Innozenz IV. blieb bei seiner Haltung (Frieden nur mit allen Beteiligten), so daß der Kaiser schließlich eine Rückkehr zum Status des Jahres 1239 anbot. Die sich anbahnende Einigung vereitelte Kardinal Rainer von Viterbo, indem er einen Aufstand gegen die kaiserliche Besatzung in seiner Heimatstadt inszenierte, die einen gescheiterten Angriff kaiserlicher Truppen provozierte. Für den Papst war der Aufstand äußerst ungelegen, weil er ihn als Friedensstörer disqualifizierte. Auf seine Vermittlung wurd eein Kompromiß geschlossen: das Heer sollte abziehen, dafür erhielt die Besatzungstruppe freies Geleit aus der Stadt. Allerdings fielen die Einwohner von Viterbo, durch ihren Kardinal angestachelt, über die abziehenden Soldaten her und brachten sie um. Friedrich II. schwor ewige Feindschaft und stellte seine Rache nur aus taktischen Erwägungen für eine Weile zurück.
Weitere Verhandlungen, Anfang 1244 aufgenommen, führten am 30. März 1244 zu einem Vorvertrag in Rom, den allerdings die Lombarden nicht anerkannten. Außerdem wollte Friedrich II. erst nach Lösung des Bannes den Kirchenstaat räumen, während Innozenz IV. den sofortigen Abzug verlangte. Daraufhin verstärkte der Kaiser seine Stellung und arbeitete auf einen Umsturz in Rom hin. Ein letzter Verusch zur Rettung des Friedens - das Angebot eines persönlichen Gespräches zwischen Kaiser und Papst - scheiterte an dem Gerücht, Innozenz IV. solle bei diesem Gespräch gefangen genommen werden. Am 7. Juli 1244 floh der Papst aus Rom nach Genua, blieb dort bis Oktober und reiste von dort weiter nach Lyon. Diese Flucht war für Friedrich II. ungünstig: die Schuld wurde ihm zugesprochen und Innozenz IV. hatte eine erheblich erweiterte Bewegungsfreiheit.
Von Lyon aus berief Innozenz IV. das bereits von Gregor IX. geplante Konzil ein, auf dem der Kaiser abgesetzt werden sollte. Friedrich II. machte im Frühjahr ein letztes, überraschendes Angebot und gab in allen Punkten nach: der Papst solle die Lombardenfrage entscheiden, er sagte zu, den Kirchenstaat sofort zu räumen und verpflichtete sich zu einem sofortigen Kreuzzug von mindestens drei Jahren. Bei Nichteinhaltung einer dieser Bedingungen wollte er auf alle Herrschaft verzichten. Dieses erstaunliche Nachgeben des Staufers konnte Ausdruck der Resignation, eine Folge der Vermittlung des Patriarchen Albert von Antiochien oder ein verzweifelter Versuch, der Absetzung in Lyon zu entgehen. Innozenz IV. konnte diese Erfüllunh aller seiner Forderungen nicht zurückweisen und erteilte am 6. Mai 1245 dem Patriarchen Albert den Auftrag, Friedrich II. vom Bann zu lösen. Doch auch dieser Friedensschluß verlief im Sand, angeblich wegen einiger Übergriffe des kaiserlichen Heeres im Kirchenstaat (während einer Verwüstung Viterbos beim Zug zum Reichstag nach Verona), die Kardinal Rainer von Viterbo aufgebauscht hatte.
Am 26. Juni 1245 trat das Erste Allgemeine Konzil von Lyon zusammen, zu dem zwar alle Prälaten der Christenheit geladen waren, auf dem aber nur etwa 150 erschienen (Drittes Laterankonzil: über 400). Die Deutschen und Ungarn fehlten völlig, ebenso die Italiener aus den kaisertreuen Gebieten. Die meisten Konzilsväter stammten aus England, Frankreich und Spanien und waren wegen der Gefangennahme von 1241 noch entrüstet. Der Großhofrichter Thaddäus von Suessa sollte den Kaiser verteidigen, die Anklage übernahm Kardinal Rainer von Viterbo. Der einzige Erfolg des kaiserlichen Beauftragten war eine 12tägige Verschiebung der Schlußsitzung. Die Sitzung am 17. Juli 1245 versuchte er wegen juristischer Formfehler anzufechten, ws ihm nicht gelang. Innozenz IV. trug die Liste der Verbrechen des Kaisers vor (Meineid, Friedensbruch, Sakrileg und Häresie) und erklärte ihn für abgesetzt. Jeder, der ihm in Zukunft noch beistehe, sei exkommuniziert. In dieser Situation versuchte Friedrich II., die bis dahin papstfreundlich gesinnten Bettelmönche (Dominikaner, Franziskaner u.a.) auf seine Seite zu ziehen, indem er ihre Armutsforderungen öffentlich unterstützte und den Prunk der Kurie anklagte. Die Anschuldigungen fielen auf fruchtbaren Boden: die einflußreichen Orden traten zu ihm über und bezeichneten den Papst als Ketzer, die hohen Geistlichen als Simonisten.
Schon vor dem Lyoner Konzil hatte der Papst einen propagandistischen Kampf auf allen Fronten in Deutschland, Sizilien und Italien geführt. Allerdings standen die deutschen Fürsten fest auf der Seite des Kaisers, erst nach der Absetzung 1245 fielen der Kölner und der Mainzer Erzbischof von ihm ab (wobei die Absetzung nur ein Vorwand war, tatsächlich standen territioriale Wünsche der geistlichen Fürsten im Vordergrund). So konnte der Papst in die bis dahin geschlossene Reichskirche eindringen, wichtige Ämter mit Getreuen besetzen und Mönche zur Verbreitung des Banns auf Reichsgebiet schicken. Sogar der Kreuzzugsgedanke wurde für den Kampf gegen Friedrich II. zurückgestellt (was Innozenz IV. später große Probleme bereiten sollte). Nachdem sich auch der Trierer Erzbischof gegen den Staufer gestellt hatte, wurde am 26. Mai 1246 der Thüringer Landgraf Heinrich Raspe in Veitshöchheim von den drei rheinischen Erzbischofen zum Gegenkönig gewählt. Er wurde von keinem weltlichen Fürsten unterstützt („Pfaffenkönig“) und starb bereits am 26. Februar 1247 noch vor seiner offiziellen Krönung. Damit war die Papstpartei in Deutschland in Schwierigkeiten, nur der Herzog Heinrich II. von Brabant unterstützte sie und schlug seinen Neffen Wilhelm von Holland als neuen König vor. Wilhelm wurde am 3. Oktober 1247 gewählt und machte mühsame Fortschritte: Aachen mußte ein halbes Jahr belagert werden, bis im November 1248 die Krönugn stattfinden konnte. Auch danach blieb Wilhelms Gebiet auf die rheinischen Erzbistümer beschränkt.
Nicht nur das deutsche, auch das sizilische Reich war fest in staufischer Hand, so daß Italien zum Hauptschauplatz der weiteren Auseinandersetzungen wurde. Dort gab es auch in den kaiserlichen Gebiten stets eine starke guelfische Opposition. Eine Verschwörung gegen das Leben des Kaisers scheiterte, die Flucht einiger Verschwörer nach Rom und das in Deutschland von papstfreundlichen Kräften verbreitete Gerücht, der Kaiser sei gestorben, legte den Schluß nahe, Innozenz IV. sei eingeweiht. Dadurch erhielt das Ansehen des Papstes einen schweren Schlag, Viterbo trat zum Kaiser über, Venedig näherte sich ihm an. Friedrich II. Position verbesserte sich stetig, er setzte nur noch uneheliche Söhne und Schwiegersöhne als Generalvikare ein und verfolgte offenbar die Umwandlung Italiens in eine Art staufischen Familienbesitz.
Anfang 1247 hielt er seine Position in Italien für stabil genug, um einen großen Feldzug nach Lyon und weiter ins deutsche Reich in Angriff zu nehmen. Von Sizilien aus zog er mit einem starken Heer nach Turin, um von dort aus über die Alpen Lyon zu erreichen, aber die Nachricht vom Abfall Parmas ließ ihn den Zug abbrechen. In Eilmärschen zog das kaiserliche Heer nach Parma, wo der päpstliche Legat Gregor von Montelongo den Widerstand leitete. Der Kaisersohn Enzio wartete vor Parma bereits auf seinen Vater, der allerdings keine Erstürmung der Stadt versuchte, sondern sich auf eine längere Belagerung einstellte. Spätere Quellen nehmen an, zu diesem Zeitpunkt sei eine Eroberung noch möglich gewesen, erst der Aufschub habe den Parmensern die Gelegenheit zur weiteren Befestigung der Stadt gegeben. Der Abfall Parmas war ein Signal, überall in Italien begannen guelfische Erhebungen, ein Zeichen für die Labilität der scheinbar soliden Position Friedrich II. Teile des großen Heeres wurden in die Provinzen geschickt, um die Aufstände zu bekämpfen, während der Kaiser bei Parma die feste Lagerstadt Victoria errichten ließ, womit die letzten Versorgungsmöglichkeiten Parmas abgeschnitten wurden. Die Situation war für die Belagerten kritisch, es blieb nur die Alternative einer bedingungslosen Kapitulation (und anschließender Zerstörung) oder eines verzweifelten Angriffs.
Als Friedrich II. mit einigen Offizieren auf der Jagd war, griff ein Regiment Victoria an. Der Kommandant zog mit dem Großteil des Heeres aus und entblößte die Stadt, die hinter seinem Rücken von der Hauptmacht der Parmenser zerstört wurde. Der zurückkehrende Kaiser konnte mit seinen wenigen Begleitern nichts mehr ausrichten und floh nach Cremona, wo er das zerschlagene Heer sammelte. Zwar zog er nochmal gegen Parma, beschloß aber auf den Trümmern Victorias, die Belagerung zu beenden. Das bedeutete eine entscheidende Niederlage Friedrich II., die zwar das militärische Kräfteverhältnis nicht wesentlich veränderte, aber eine große psychologische Wirkung hatte und dem Kaiser den Nimbus der Unbesiegbarkeit nahm. Seine Gegner erhielten Auftrieb, Ravenna und fast die gesamte Romania fielen von ihm ab.
In den treu gebliebenen Gebieten wurden neue Steuern eingezogen und Truppen ausgehoben, so daß der militärische Verlust bald ausgeglichen war. König Ludwig IX. der Heilige von Frankreich versuchte sich als Vermittler zwischen Papst und Kaiser, um sich die Unterstützung des Kaisers für seinen bevorstehenden Kreuzzug zu sichern, scheiterte allerdings an der unnachgiebigen Haltung Innozenz IV., dem die Vernichtung des Staufers wichtiger war als die Rückgewinnung des Heiligen Landes. Nachdem er sich wieder konsolidiert hatte, plante Friedrich II. einen neuen Lyonzug, als er Ende 1248 in Cremona vom Verrat seines engsten Vertrauten des Großhofjustitiars Petrus de Vinea erfuhr. Worin der Verrat genau bestand, ist unklar, wahrscheinlicher als ein Übertritt zum Papst ist die persönliche Bereicherung durch Enteignungen angeblicher Staatsfeinde (was unter einem Regime, das die staatliche Gerechtigkeit fördern wollte, tatsächlich Hochverrat darstellte). Petrus de Vinea beging Selbstmord, bevor er verurteilt wurde. Auslöser des Verfahrens gegen ihn war wahrscheinlich ein Giftmordanschlag des kaiserlichen Leibarztes, an dem er allerdings unbeteiligt war. Der Fall des Großhofjustitiars zeigte, wie mißtrauisch Friedrich II. auch gegenüber seiner engsten Umgebung geworden war.
Von Cremona zog der Kaiser nach Neapel. Hier erhielt er die Nachricht von der Gefangennahme seines Sohnes Enzio durch bolognesische Truppen am 26. Mai 1249. Er bemühte sich sehr um die Freilassung, drohte den Bolognesern und machte ihnen große Versprechungen, da er große Hoffnungen auf seinen Sohn gesetzt hatte. Trotz allem blieb Enzio bis zu seinem Tod 1272 in Haft, überlebte also die gesamte staufische Dynastie. Erneut erhielten die Kaisergegner Auftrieb, viele Städte traten zu ihnen über, von Apulien aus arbeitete Friedrich II. entgegen. Ende 1249 hatte er Erfolg, ein Angriff auf sizilische Gebiete wurde abgeschlagen, die Mark Ancona, das Herzogtum Spoleto und Ravenna kehrte auf seinen Seite zurück. Nachdem auch Piacenza kaiserlich geworden war, konnte Parma vernichtend geschlagen werden.
In Deutschland zwang Konrad IV. im Sommer 1250 die rheinischen Erzbischöfe zu einem Waffenstillstand. Gleichzeitig gab der in die Gefangenschaft des Sultans geratene Ludwig IX. von Frankreich dem Papst die Schuld am Scheitern seines Kreuzzuges, weil dieser sich gegen einen Frieden mit Friedrich II. gestellt hatte. Die Planungen für den Deutschlandzug des Staufers wurden jetzt konkreter, da auch der griechische Kaiser Truppen zum Kampf gegen die Kurie geschickt hatte. Ende August 1250 erkrankte er allerdings in Foggia schwer. Er erkannte den Ernst der Lage und setzte in Fiorentino sein Testament auf. Die Herrschaftsrechte wurden unter den Söhnen aufgeteilt: Konrad IV. sollte der Erbe des Imperiums (der Kaiserwürde) und des sizilischen Reiches werden (im Fall seines kinderlosen Tod ginge die Herrschaft auf die Söhne Heinrich oder Manfred über). Manfred erhielt das Fürstentum Tarent und bei Abwesenheit Konrad IV. die Reichsverweserschaft in Italien. Heinrich bekam das Königreich Arelat (in Burgund) oder Jerusalem. Der Sohn des gestorbenen Heinrich (VII.), der Kaiserenkel Friedrich wurde zum Herrscher über Österreich und die Steiermark bestimmt. Die Kirche sollte alle Besitzungen und Rechte in Italien zurückerhalten, dafür die Reichsrechte anerkennen. Für alle Gegner des Kaisers wurde Amnestie (außer bei Hochverrat) erlassen. Die Verwaltung des sizilischen Reiches sollte wie unter dem letzten normannischen König Wilhelm II. gestaltet werden. 100.000 Goldunzen aus dem Erbe des Kaisers gingen als Geschenk an die Christen im Heiligen Land, 500 Goldunzen an die Hauptkirche in Palermo, in der Friedrich II. neben seiner ersten Frau Constanze und seinen Eltern begraben werden wollte. Dieses Testament ist nur als Abschrift aus der Zeit nach dem Tod des Kaisers erhalten.
Trotz seines jahrzehntelangen Kampfes gegen die katholische Kirche starb Friedrich II. als christlicher Kaiser am 13. Dezember 1250. Er erhielt von Erzbischof Berath von Palermo die Sakramente starb entsündigt. Sein Sohn Manfred brachte den Leichnam nach Palermo, wo er wie gewünscht bestattet wurde. Im Februar 1251 wurde er in den eigentlich für den normannischen König Roger II. gedachten Sarg umgebettet. Kurz vor seinem Ende hatte Friedrich II. seinen Erben noch geraten, den Tod möglichst lange geheimzuhalten, um Aufstände zu vermeiden. Die Geheimhaltung führte auch dazu, daß in Deutschland später mehrfach „falsche Friedriche“ auftraten und sich als Kaiser ausgaben. Um den toten Herrscher bildete sich die Kyffhäusersage, nach der er in einem Berg ruhend auf die Erneuerung des Reiches wartete.