В своем объединительном движении мусульмане должны были рано или поздно прийти в столкновение с Византией, подчинившей своему влиянию северо-запад Аравийского полуострова. Это и случилось в 629 г. В этом году Мухаммед отправил посла ал-Хариса-ибн-Умайра ал-Азди к арабскому правителю города Бусры (Бостры) в Заиорданье. (Имени этого правителя источники не называют.) В пути посол был задержан и убит другим арабским правителем, находившимся на службе у византийцев, Шурахбилем-ибн-Амром (видимо, из чувства соперничества с упомянутым правителем Бусры).

В ответ на это убийство Мухаммед отправил против Шурахбиля трехтысячный отряд под командой своего приемного сына Зейда-ибн-Харисы, который был наголову разбит объединенным войском ромеев и союзных им арабов в сражении при Муте к востоку от Мертвого моря в сентябре 629 г. Зейд и два других военачальника погибли, и лишь небольшая часть мусульман сумела спастись бегством.

Так плачевно для мусульман окончилось их первое военное столкновение с Византией. Вряд ли Мухаммед, по крайней мере в первое время после сражения при Муте, думал о новых набегах на византийские владения, тем более что тогда объединение Аравии далеко еще не было завершено. Но в этот момент византийское правительство совершило крупную политическую ошибку. Считая, что после сражения при Муте арабы никогда уже больше не осмелятся напасть на империю, и испытывая финансовые затруднения, оно прекратило выплату жалованья арабам, состоявшим на службе у ромеев и охранявшим пограничную территорию на краю пустыни, причем сделано это было в весьма грубой форме. Когда арабы-пограничники пришли к чиновнику-евнуху, распределявшему воинское жалованье, он сказал, что император едва дает жалованье воинам, и прогнал арабов, назвав их при этом псами, чем нанес гордым сынам пустыни сильное оскорбление. Оскорбленные арабы начали покидать пределы империи и переходить к своим мусульманским соплеменникам.