While still engaged in bringing security and order to the distant regions of the Peninsula, the news reached Muhammad that Byzantium was mobilizing an army to invade the northern approaches of Arabia to avenge the last engagement at Mu'tah. It was also rumored that this imperial army would seek to stamp out the nascent power of the Muslims who now stood at the frontier of both the Byzantine and Persian empires. At once and without hesitation, the Prophet decided that the imperial army must be met and destroyed so completely that the Byzantines would not think again of attacking Arabia or interfering in its affairs. It was autumn, but the desert heat, being greater in the beginning of autumn than in summer, was all the more deadly. Moreover, a long distance separated Madinah from al Sham. Any venture to cross it required great amounts of water and provisions. Inevitably, therefore, Muhammad had to tell the people of his plan if they were to prepare themselves adequately. Equally, it was necessary this time to alter his old diversionary strategy of ordering the army to march in the opposite direction, for no such expedition as he was preparing for could be kept a secret. Indeed, Muhammad sent messengers to all the tribes asking them to mobilize the greatest army ever, and to the Muslims of large means everywhere to give liberally for the equipment of the army. The Muslim force, the Prophet decided, should be so large and preponderous as to overwhelm an enemy long known for their numbers and military equipment.
How were the Muslims to receive this new call to leave their families and properties in the height of summer heat, to venture in desolate and waterless deserts, and to confront an enemy powerful enough to defeat Persia and even too mighty to be defeated by the Muslims? Would their Islamic conviction, love for the Prophet, and loyalty to God's religion inspire them to give up wealth, armour, and life, and to do so in such proportion as to instill terror in the heart of such an enemy? Or, would the discomforts of desert and summer heat, of thirst and hunger, force them to sit back and refuse to move? In those days, Muslim ranks included two kinds of people: those who entered Islam with hearts full of guidance and light and minds certain of their convictions, and those who did so in search of material gain or out of fear of Muslim arms. Those who belonged to the former group volunteered their own persons and offered all the equipment they could muster. They put themselves and their wealth entirely at the Prophet's disposal. Among them were the poor who walked on foot and the wealthy who provided for themselves and others, All hoped for martyrdom and closeness to God. The other group complained and looked for excuses to justify their recalcitrance. Secretly, they derided Muhammad's call to arms and ridiculed its timing and strategy. These were the munafiqun about whom Surah "Al Tawbah" had spoken. How great was its call to jihad! And how terrible the punishment it promised to he who failed to answer the Prophet's call!
While Muhammad was busy settling the affairs of Madinah-handing over the reins of government to Muhammad ibn Maslamah, appointing `Ali ibn Abu Talib as guardian of his household and giving to each the necessary instructions-he left the army under the command of Abu Bakr. The latter led the assembled men in prayer, and when the Prophet returned, he handed the command back to him. Responding to Muhammad's call, `Abdullah ibn Ubayy came out at the head of a little band of soldiers and asked for permission to march alongside the Muslim army. The Prophet, however, preferred that `Abdullah stay in Madinah, for he was not quite sure of his good faith. At Muhammad's command, the army began its march, raising great dust and making a tremendous roar. The people of Madinah hurried to the rooftops to see this great mass of men, animals, and equipment move toward al Sham. They were anxious to catch a glimpse of this large mass of humanity venturing out against heat, thirst, and all kinds of hardship in order to fulfill their duty to God and to win His pleasure, the pleasure which they had deemed worthier than all the good things they had left behind. Indeed, the sight of this army on the march pioneered by ten thousand cavalrymen and the stupefied people of Madinah watching it, moved to action those whom the very command of the Prophet failed to stir. Such was the case of Abu Khaythamah who, after seeing the Muslim army, went straight to his house where each of his two wives had cooked for him a delicious meal, drew some fresh water to drink, and sprinkled the tent and surroundings to cool off the place. Abu Khaythamah could not advance into his own house a single step before exclaiming, "The Prophet of God is battling the heat, sand, and thirst of the desert and I, Abu Khaythamah, languish in the cool, eat delicious food, and enjoy the company of beautiful women? No, by God, that cannot be! Prepare for me quickly some provisions that I may join him." He shot off like an arrow. There were probably many more who did likewise after realizing the shame that would befall them if they remained in the city.
The army then marched in the direction of Tabuk. News of its approach had already reached the Byzantines who immediately withdrew to the safety of their hinterland. When Muhammad learned of their fear and withdrawal, he saw no reason to pursue them within their territory. Instead, he roamed over the border inviting all either to fight or befriend him. His purpose was to secure the frontiers of Arabia. Yuhanna ibn Ru'bah, Governor of Aylah, received such an invitation. He came in person carrying a golden cross, presented gifts, declared his submission, and handed over the keys of his island to the Prophet. So did the people of al Jarba' and Adhruh, and they all paid the jizyah. The Prophet gave each of them a covenant which read as the following document given to Yuhanna. "In the name of God, the Merciful, the Compassionate. This is a covenant of security granted under God by Muhammad, the Prophet of God, to Yuhanna ibn Ru'bah and the people of Aylah. Their ships, vehicles, and routes on land and on sea are secure under God's guaranty and Muhammad's. So are all those who accompany them whether of the peoples of al Sham, Yaman, or beyond the seas. Whoever among them perpetrates a crime shall be liable for it in his own person, and it shall be legitimate for Muhammad to confiscate his wealth. It shall not be legitimate to prevent any one of them from using a well or a road on land or sea which they have been in the habit of using." When the Prophet applied his seal to the document, he presented Yuhanna with a mantle woven in Yaman and showed him every courtesy, respect, and friendship. It was further agreed that Aylah would remit a yearly jizyah of three hundred Dinars.
With the withdrawal of the Byzantines and the binding of the frontier provinces with treaties and covenants of peace, Muhammad had no reason to march any further. The only one he feared was Ukaydir ibn 'Abd al Malik al Kind!, the Christian prince of Dumah. This prince was suspected of preparing to launch a treacherous attack as soon as the Byzantine forces could return. Taking no chances, Muhammad sent Khalid ibn al Walid with five hundred cavalrymen to deal with this threat and commanded the army to return to Madinah. Khalid hurried to Dumah and, discovering that its king was out on a hunting trip with his brother Hassan, attacked it without finding any appreciable resistance outside the city; its gates, however, remained tightly closed. Khalid seized Ukaydir and his brother Hassan as they returned home. He killed Hassan and threatened to kill Ukaydir unless the gates of the city were opened. Ukaydir and his city yielded. After seizing two thousand camels, eight hundred goats, four hundred loads of grain, and four hundred coats of arms, Khalid carried them, together with his captive, Prince Ukaydir, to Madinah. Muhammad offered Islam to Ukaydir, and the latter converted. He was then reinstated on his throne and became the Prophet's ally.