Podczas siedmioletniego pobytu w Pradze nawiązał rozległe kontakty z radykalnymi antytrynitarzami w Czechach (Bracia czescy) i Polsce (Bracia polscy).
Jego karierę zakończył wybór w 1566 Michele Ghislieriego, kierującego dotychczas inkwizycją, na papieża. Już jeden z jego pierwszych aktów jako papieża zawierał żądanie ekstradycji Paleologa. 30 marca 1571 Paleolog został zaaresztowany, po czym spędził cztery miesiące w lochu praskim. Jednakże uciekł kolejny raz, sprzedał swój dom, pobrał ostatnią pensję i wyjechał tym razem do Polski.
W Polsce Paleolog był przekonany, że znana z tolerancji religijnej Rzeczpospolita Obojga Narodów udzieli mu dożywotniego schronienia. Zamieszkał w Krakowie i przyłączył się do tamtejszego zboru braci polskich.
Korzystając z liberalnego polskiego prawa do naturalizacji, stał się poddanym polskim, znanym jako Jakub Paleolog. W Krakowie skontaktował się z Andrzejem Dudyczem, innym naturalizowanym Polakiem, dawnym katolickim biskupem Peczu na Węgrzech, który również popierał doktrynę braci polskich. Paleolog uczestniczył aktywnie w debatach religijnych braci polskich. Walczył z ekstremistycznymi poglądami (zakaz własności prywatnej, służby wojskowej i obejmowania urzędów państwowych), utrzymując, że są to poglądy przesadne.