Con tale intendimento, senza comunicare ad alcuno il suo pensiere, nel 1279 si recò in Costantinopoli. Incontrati ivi due cavalieri del regno, che, per essere anch’essi nemici di Carlo, colà s’erano ridotti, disse loro: esser profugo anch’esso e per la stessa cagione; pregarli a far modo potesse entrare al servizio del greco imperadore. Coloro accettarono l’incarico, e dissero al Paleologo d’esser venuto da Sicilia, per trovar servizio nella sua corte, un signore di gran senno, valente medico; l’imperadore ne fu lieto; avuto a se il Procida, grandemente l’onorò; gli diede la carica di suo primo consigliere (514).
      Dopo tre mesi che vivevano in grande dimestichezza, un dì messer Giovanni disse al Paleologo: volergli parlare di cosa d’altissimo rilievo, in luogo secretissimo. Ridottisi sopra una torre, ov’erano le secreterie dell’impero, il siciliano disse al greco: Comechè altri vi tenga principe savio e prode, io vi reputo il più vile degli uomini e simile a quei torpidi animali, che non si risentono, se non quando sono traforati dalle punture. Come potete voi musare, mentre Carlo d’Angiò è per venirvi addosso con prepotenti forze, risoluto a togliervi l’impero e la vita? A ciò il Paleologo, piangendo rispose: O messer Giovanni, io ho tentato tutte le vie per distogliere l’Angioino dal suo proponimento; ho cercata la mediazione del papa, de’ cardinali de’ re di Francia, d’Inghilterra, di Spagna e d’Aragona; invano: per esser tutti spauriti delle grandi forze di lui. Solo Dio può ajutarmi; chè dagli uomini non posso sperare aiuto.