Quaranta conti avevano promesso d'unirsi alla crociata, e dieci mila cavalli si allestivano sotto i suoi ordini. Nello stesso tempo negoziava col doge Giovanni Dandolo, segnava un trattato, in forza del quale la repubblica di Venezia obbligavasi a prendere parte alla crociata, mandando lo stesso doge con quaranta galere armate in guerra396. Queste forze sembravano sufficienti per distruggere l'impero greco, e Paleologo aveva più volte esperimentato l'impetuoso valore dei Latini, e la viltà delle sue truppe. Procida facendogli conoscere il pericolo che gli sovrastava, gli offrì nello stesso tempo di eccitare negli stati del suo nemico una ribellione che non gli permettesse di pensare per molto tempo a guerre straniere. Gli offriva inoltre di mettere Carlo in guerra con una nazione non meno valorosa della Francese, una nazione la di cui formidabile infanteria non lascerebbesi spaventare o rovesciare dall'urto degli uomini d'armi. La sola cosa ch'egli chiedeva a Paleologo era del denaro per supplire alle spese della spedizione degli Arragonesi, e per comperare armi ai Siciliani ribellati.
      (1280) Nicolò III governava ancora la Chiesa, e Paleologo che con tanti sagrificj erasi riconciliato colla santa sede, non voleva perdere la sua protezione. Accordò un primo soccorso di danaro a Procida, esigendo che non si facesse la ribellione di Sicilia senza l'assenso del papa397. Giovanni, che viaggiava sotto mentito abito di monaco francescano, tornò a Malta con un segretario dell'imperatore greco.