Musnad Ahmad 407:1

Abdullah ibn Ahmad said: Surayj ibn Yunus narrated to us, from his book, he said: Abbad ibn Abbad—meaning al-Muhallabi—narrated to us, from Abdullah ibn Uthman ibn Khuthaym, from Sa’id ibn Abi Rashid, a freedman of the family of Mu’awiyah, who said: I arrived in al-Sham, and it was said to me: "In this church is the messenger of Caesar to the Messenger of Allah, may Allah bless him and grant him peace." He said: So we entered the church, and there I was with an old man. I said to him: "Are you the messenger of Caesar to the Messenger of Allah, may Allah bless him and grant him peace?" He said: "Yes." He said: I said: "Tell me about that." He said: "When he (the Prophet) campaigned to Tabuk, he wrote a letter to Caesar and sent it with a man called Dihyah ibn Khalifah. When he (Caesar) read his letter, he placed it with him on his throne, and he sent for his patriarchs and the heads of his companions. He said: 'This man has sent a messenger to you and has written a letter to you, giving you a choice of one of three things: either you follow him in his religion, or you acknowledge for him a tribute that flows to him from you while he leaves you in your state in your lands, or you cast war upon him.' He said: They snorted a snort, such that some of them came out of their cloaks, and they said: 'We will not follow him in his religion and abandon our religion and the religion of our fathers, nor will we acknowledge for him a tribute that flows to him from us, but we will cast war upon him.' He said: 'That was what I expected, but I disliked acting on my own authority regarding a matter without you.'" Abbad said: I said to Ibn Khuthaym: "Had he not approached and intended Islam, according to what has reached us?" He said: "Yes, were it not that he saw [the reaction] from them." He said: He (Caesar) said: "Find me a man from the Arabs so that I may write with him a reply to his letter." He said: "I was brought, and I was a young man, so he took me to him. He wrote his reply, and he said to me: 'Whatever you forget of anything, memorize three things from me: Observe when he reads my letter whether he mentions the night and the day, and whether he mentions his letter to me, and observe whether you see a mark on his back.'" He said: "So I set out until I came to him while he was in Tabuk, in a circle of his companions, whispering. I asked, and I was informed of him, so I handed the letter to him. He called for Mu’awiyah, who read the letter to him. When he reached his (Caesar's) statement: 'You have invited me to a Paradise whose width is the heavens and the earth, so where is the Fire?' The Messenger of Allah, may Allah bless him and grant him peace, said: 'When the night comes, where is the day?'" He said: He (the Prophet) said: "I wrote to the Negus, and he tore it up, so Allah tore him up, the tearing of a kingdom." Abbad said: I said to Ibn Khuthaym: "Had the Negus not accepted Islam, and the Messenger of Allah, may Allah bless him and grant him peace, announced his death in Medina to his companions and prayed over him?" He said: "Yes, that was so-and-so son of so-and-so, and this was so-and-so son of so-and-so." Ibn Khuthaym mentioned them both, but I forgot them. "And I wrote a letter to Chosroes, and he shredded it, so Allah shredded him, the shredding of a kingdom. And I wrote a letter to Caesar, and he replied to me in it, and the people will not cease to fear their might as long as there is good in life." Then he said to me: "From whom are you?" I said: "From Tanukh." He said: "O brother of Tanukh, do you have any interest in Islam?" I said: "No, I have come from before a people, and I am among them upon a religion, and I will not exchange their religion until I return to them." He said: The Messenger of Allah, may Allah bless him and grant him peace, laughed or smiled. When I had fulfilled my need, I stood up. When I turned away, he called me and said: "O brother of Tanukh, come here and proceed with what you were commanded." He said: "I had forgotten it." So I turned around from behind the circle, and he cast off a cloak that was upon his back, and I saw the cartilage of his shoulder like a large cupping glass.