In 953, following a spate of undiplomatic letters between the two rulers, he served as ambassador for Abd al-Rahman III to German King (and future Holy Roman Emperor) Otto I.
In Germany, he successfully normalised relations between the nominal rulers of Christendom and Islamdom.
It was while in Germany (956) that he met Liutprand of Cremona, the Italian bishop and diplomat, and convinced him to write a history of the times.
He continued his work as an ambassador to Christendom, going to the other European emperor in Constantinople, and then to Jerusalem, the holiest city in the three great monotheistic faiths (Christianity, Islam, and Judaism).
In 961, Recemundus presented an Arabic calendar of Christian holidays (including some commemorating the Martyrs of Córdoba) to the new caliph, al-Hakam II.