وانطلق الجيش بعد ذلك قاصدا تبوك، وكانت الروم قد بلغها أمر هذا الجيش وقوته، فاثرت الانسحاب بجيشها الذي كانت وجّهت إلى حدودها ليحتمي داخل بلاد الشام في حصونها. فلما انتهى المسلمون إلى تبوك وعرف محمد أمر انسحاب الروم ونمي إليه ما أصابهم من خوف، لم ير محلّا لتتبّعهم داخل بلادهم.

وأقام عند الحدود يناجز من شاء أن ينازله أو يقاومه، ويعمل لكفالة هذه الحدود حتى لا يتخطى من بعد ذلك إليها أحد. وكان يوحنا بن رؤبة صاحب أيلة أحد الأمراء المقيمين على الحدود. ولقد وجّه إليه النبيّ رسالة أن يذعن أو يغزوه فأقبل يوحنّا وعلى صدره صليب من ذهب، وقدّم الهدايا والطاعة، وصالح محمدا وأعطاه الجزية، كما صالحه أهل الجرباء وأذرح وأعطوه الجزية. وكتب رسول الله لهم كتب أمن، هذا نص أحدها- وهو ما كتب ليوحنا: «بسم الله الرحمن الرحيم. هذه أمنة من الله ومحمد النبيّ رسول الله ليوحنة بن رؤبة وأهل أيلة سفنهم وسيّارتهم في البر والبحر لهم ذمّة الله ومحمد النبيّ ومن كان معهم من أهل الشام وأهل اليمن وأهل البحر. فمن أحدث منهم حدثا فإنه لا يحول ماله دون نفسه، وإنه طيّب لمحمد أخذه من الناس. وإنه لا يحلّ أن يمنعوا ماء يردونه ولا طريقا يريدونه من برّ أو بحر».

وإيذانا بالموافقة على هذا معهد أهدى محمد إلى يوحنا رداء من نسج اليمن وأحاطه بكل صنوف الرعاية، بعد أن اتّفق على أن تدفع أيلة جزية قدرها ثلاثمائة دينار في كل عام.