Mohammed the man was a great general, who fought his contemporary, the Byzantine Emperor Heraclius. The latter had once been a great general, but was by then too ill to lead his army in later life.
A letter from the Muslim is said to have reached the Christian in Jerusalem, where he was celebrating a victory over the Persians. Most Byzantine emperors tended to emphasise their Roman origins, styling themselves Imperator, or Augustus. After defeating the Persians, Heraclius took on their title, and became "King of Kings" - subsequently espousing the Greek "Basileus" (king). Other Byzantine Emperors turned back messengers with letters addressed to them as Greek Emperor - until they were too desperate to refuse, with the Ottomans at their gates.
Apparently some of Mohammed's letters survive, including this one to Heraclius: "A tradition tells: Prophet Mohammed wrote a letter to Heraclius, asking him to embrace Islam. The letter, written on gazelle hide, is in the Hashemiya Palace, near Amman. King Hussein of Jordan is said to be a direct descendant from the prophet Mohammed. A special mosque will be built where the letter of Mohammed to Emperor Heraclius will be on exhibition. (Jerusalem Post, April 13, 1977)" An Islamic interpretation of it can be found here. (image)