Después de regresar, y todavía sin tener su amor respondido, decidió partir hacia Tierra Santa.

Palman y su séquito cruzaron Zeta, una provincia marítima del Reino de Serbia, en manos del rey joven (heredero) Esteban Uroš IV Dušan, y decidieron unirse a su servicio como mercenarios.

[1]​ En enero o febrero de 1331, Dušan estaba peleando con su padre, el rey Esteban Uroš III,[2]​ quizás presionado por la nobleza.

[2]​ Tres meses después, Uroš III ordenó a Dušan que se reuniera con él.

Isabel, a quien no pidieron su consentimiento, se horrorizó al pensar que la habían empujado al mundo desconocido, a una tierra bárbara del Este, para casarse con un rey de otra religión, que ya estaba casado.

Sin embargo, Cantacuceno más tarde ese año engañó a Dušan y recuperó Veria.

En marzo de 1355, un delegado papal encabezado por el obispo Pedro Tomás llegó a Serbia en una misión para convertir a los serbios al catolicismo (los serbios esperaban obtener ayuda del estado papal para organizar una cruzada contra los turcos otomanos), y Dušan, que estaba enojado con Luis I de Hungría, prohibió a los católicos de su ejército incorporarse al sermón del obispo papal.

Al escuchar que los mercenarios alemanes se unieron a un sermón, Dušan se enfureció, pero recuperó la compostura poco después, cuando su comandante, Palman, dijo que defenderían su fe, no solo aceptando el castigo sino incluso enfrentándose al ejército imperial de Dušan, si fuera necesario.