Non fu possibile venire alla scelta; Federigo pregava, minacciava, rimettea in libertà i due cardinali, che tenea prigioni; invano. Finalmente nel giugno del 1243 fu eletto il cardinal Sinibaldo dei Fieschi da Genova, che si fece chiamare Innocenzio IV. Era Federigo allora in Melfi; si vuole che, giunta colà la notizia dell’esaltazione d’Innocenzio, tutti i cortigiani ne furono lieti, per appartenere il nuovo pontefice ad una famiglia ghibellina. Solo Federigo ne fu dolente; dicea d’aver perduto un cardinale amico ed avere acquistato un papa nemico; e ben s’appose.
      Ciò non però di manco sulle prime parea che la pace da ambe le parti fosse sinceramente desiderata. Saputa la promozione di papa Innocenzio, il re imperadore a lui spedì l’arcivescovo di Palermo, il suo gran cancelliere Pietro delle Vigne ed il presidente della gran corte Taddeo di Sessa, per complire in suo nome il pontefice ed aprir trattative di pace. Furono costoro bene accolti dal papa, il quale mandò per parte sua tre nunzî a Federigo per pregarlo a mettere in libertà i prelati, che tenea prigioni; ma al tempo stesso spediva secretamente una mano dei suoi soldati ad assalire Viterbo: e venne loro facile cacciarne gl’imperiali, che v’eran di guarnigione e tutt’altro che tale assalto s’aspettavano. Per le quali cose Federigo si negò ad aderire alla dimanda del papa.
      La guerra divampò allora più fiera e le stesse calamità le davano maggiore alimento. Un’orda sterminata di Tartari avea invasa l’Europa, e dopo d’avere devastata la Russia, la Polonia e la Boemia, minacciava di progredire in Germania.