Coi cardinali che, riuniti in conclave, non riuscivano ad eleggere il successore di Celestino, Federico non era molto tenero. Così, infatti, li apostrofava: " A voi, figli di Belial, a voi, figli di Efrem, a voi, gregge di perdizione, indirizzo la parola, a voi, colpevoli di ogni umano sconvolgimento, pietra di scandalo di tutto l’universo!". Dopo oltre un anno e mezzo di vacanza, il 24 giugno 1243, dal conclave uscì finalmente eletto Papa, col nome di Innocenzo IV, il cardinale di S. Lorenzo in Lucina, Sinibaldi Fieschi, genovese dei conti di Lavagna. Giurista e teologo, era amico di Federico che, alla notizia della sua elezione pare abbia esclamato: "Di questa elezione noi abbiamo disavanzato assai, poiché costui, che ci fu amico cardinale, ci sarà nemico pontefice". Un papa, infatti, mai avrebbe potuto essere amico dell’Imperatore, per i noti conflitti di interessi politici, e questi fu veramente la sua bestia nera! Fu subito evidente come volesse mantenere la politica teocratica del suo predecessore Innocenzo III, anzi la volle esasperare fino alle estreme conseguenze, sostenendo la netta supremazia del potere spirituale su quello temporale. Iniziarono comunque le trattative per addivenire ad una giusta pace, poiché nessuno dei due voleva cedere. Federico era coadiuvato da giuristi eccellenti come Pier delle Vigne, Taddeo di Suessa e Raimondo di Tolosa. Il 31 marzo del 1243, Papa ed Imperatore giunsero a firmare i preliminari di una pace, ma subito si resero conto delle difficoltà esistenti, per via della questione lombarda, dal momento che papato e comuni erano rimasti uniti nella lotta contro l’impero. L’accordo quindi svanì miseramente sul nascere. Federico, che si trovava a Terni, cercò allora d’incontrare personalmente il Pontefice, col quale aveva intrapreso trattative per il matrimonio di una sua nipote col proprio figlio Corrado, a condizione che Innocenzo abbandonasse la protezione verso i Lombardi. Ma questi, nottetempo, travestito da soldato, da Sutri passò a Civitavecchia, da dove salpò per Genova e da lì si recò a Lione, dove giungeva il 2 dicembre del 1244. La fuga del Papa irritò notevolmente Federico che l’accusò, giustamente, di tradimento e d’essere passato dalla parte dei ribelli. Ingenuamente l’Imperatore non si rese conto che quel "furbacchione" gli stava scavando la fossa!

Intanto in Europa la situazione politica diventava preoccupante. I Turchi avevano ripreso Gerusalemme, ed i Mongoli, capitanati da Gengis-Kan, erano alle porte della Germania, dove Corrado non era in condizione di contrastarli efficacemente. Anche in Germania la situazione non era tranquilla per Federico dal momento che l’arcivescovo di Magonza ed il langravio di Turingia, Enrico Raspe, negli ultimi tempi avevano avuto strani abboccamenti con messi papali francesi. Nel nord Italia le cose non andavano meglio, visto che Federico aveva imposto il programma amministrativo già in vigore nel regno di Sicilia, ed erano scoppiato parecchi malumori.

Il Papa da Lione, il 3 gennaio 1245, indisse il Concilio, invitando l’Imperatore a comparirvi per discolparsi delle solite accuse. Invano Federico tentò di bloccare il concilio, quindi come risposta indisse una dieta a Verona cui parteciparono i principi tedeschi, i ghibellini italiani, Ezzelino da Romano e Uberto Pallavicino. Nel frattempo il 28 giugno ebbe inizio il concilio a Lione, con molti prelati francesi e spagnoli, di tendenza guelfa, e pochi italiani e tedeschi, favorevoli a Federico. Questi mandò in sua rappresentanza Pier delle Vigne e Taddeo di Suessa. Invano questi cercarono di ritardare il concilio in attesa che si presentasse l’Imperatore che, partito per Lione, si era fermato a Torino; ragion per cui il 17 luglio fu pronunciata la scomunica contro Federico, reo di persecuzione verso la Chiesa. Si dichiarava Federico decaduto, si chiedeva l’elezione di un nuovo imperatore, ed i sudditi era sciolti dal vincolo dell’ubbidienza. Pronunciata la sentenza, i cardinali in segno di esecrazione, rovesciarono le candele che tenevano accese, mentre Taddeo di Suessa fuggì dal concilio percuotendosi il petto ed esclamando: "Giorno d’ira è questo, giorno di sangue e di sventura!".

La lotta tra Papa ed Imperatore continuò furiosa, con lo scambio reciproco di accuse e polemiche. A seguito degli intrighi di Innocenzo IV, in Germania fu eletto antirè, da un’assemblea di preti, il langravio di Turingia, Enrico Raspe, che raccoglieva intorno a sé i prelati della Renania, mentre le città rimasero fedeli all’Impero.

In Italia i guelfi continuavano una lotta sotto forma di crociata, e fecero fallire un attacco congiunto di Federico ed il figlio Enzo contro Milano. Le milizie imperiali puntarono su Milano. I Milanesi si attestarono sul Ticinello, mentre Ezzelino da Romano giungeva alle loro spalle e re Enzo risaliva da Lodivecchio. Mentre Federico fu bloccato dall’accanita resistenza del legato milanese Montelongo che impedì il passaggio del fiume, accanita infuriò invece la battaglia a Gorgonzola, il 4 novembre del 1245, dove i milanesi si scontrarono con Ezzelino e re Enzo provenienti da Cassano. Il valoroso re Enzo fu fatto prigioniero, ma tornò presto libero in seguito ad uno scambio di prigionieri. L’Imperatore, impantanato nella bassa milanese, si rese conto che sarebbe stato inutile insistere oltre, e decise ch’era più saggio battere in ritirata. Tornò a Pavia il 14 novembre 1245, e dopo essersi incontrato col figlio, attraverso Lodi e Parma andò a svernare a Grosseto.

Grave fu invece l’avvenimento all’inizio del 1246. L’Imperatore si trovava a Grosseto, ospite di Guglielmo Aldobrandeschi nel Palazzo dei Comites, quando fu informato di una congiura che aveva come scopo principale di fare scoppiare un’insurrezione nel regno di Sicilia ed assassinare lo stesso Imperatore. Il capo dei congiurati era Bernardo dei Rossi, cognato di Innocenzo IV! Vi facevano parte alti funzionari del regno tra cui: Giacomo de Morra, gran giustiziere del regno, Francesco Tebaldo, podestà di Parma, Ruggero de Amicis, capitano generale, Pandolfo di Fasanella, vicario generale in Toscana. Alcuni riuscirono a sfuggire alla cattura, ma quelli catturati, chiusi in sacchi di cuoio, furono gettati a mare.

Intanto continuava lo stato di guerra latente; lo Stato pontificio perdeva Viterbo, mentre i guelfi ottenevano il principato di Taranto, che era passato a Manfredi. Federico preoccupato, per attenuare gli effetti della scomunica, fece professione di fede nelle mani dell’arcivescovo di Palermo, del vescovo di Pavia ed all’abate di Montecassino, che, anche se a lui politicamente vicini, erano pur sempre autorità ecclesiastiche di rilievo: questi, infatti, lo dichiararono "perfettamente ortodosso". Ricorse persino alla mediazione di Luigi IX, re di Francia. Ma Innocenzo IV rimaneva inflessibile ad ogni tentativo, pretendendo che l’Imperatore si recasse personalmente a Lione a professare la sua sottomissione: la qual cosa equivaleva ad una grave sconfitta politica. Federico, capito finalmente di non avere alternative di fronte alla coriacea testardaggine del Pontefice, che oramai lo teneva in pugno, pensò veramente di andare a Lione. Ma non si sa bene quali fossero le sue vere intenzioni: se per professare la sua fede al "transfuga romano" (e già si vedeva ai piedi di Innocenzo come il nonno Barbarossa ai piedi di Papa Alessandro III) o, cosa assai più verosimile, per un colpo di mano militare.

Intanto un fatto molto grave, la defezione dell’amica Parma, lo distolse da ogni proposito o intenzione di recarsi in Francia.