После Ухуда активные действия Мухаммада, как и прежде, направлены на восток. В самом начале 4 г. х. якобы в связи со сбором бану асад б. хузайма в Катане (за Ма'дин ан-Нукра в сторону Файда) под главенством Тулайхи б. Хувайлида и Саламы б. Хувайлида для нападения на Медину против них был направлен едва выживший после ранения при Ухуде мухаджир Абу Салама б. Абдаласад с отрядом в 150 или 125 человек. Численность отряда, отправлявшегося в поход за 250 км по территории недружественных племен, слишком мала для нападения на готовящегося к нападению противника. Сведения об этом походе неоднозначны: по одним сведениям, асадиты вняли увещеваниям своего соплеменника не рисковать и рассеялись, так что Абу Салама пришел к пустому месту, по другим — произошло какое-то столкновение, не имевшее серьезных последствий. Отряд вернулся через десять с небольшим дней со скромной добычей и без потерь, если не считать того, что у Абу Саламы открылась рана, он слег и через три месяца умер.
На этот период приходятся первые сведения попытках пропаганды ислама за пределами Медины. В конце 3 или начале 4 г. х. (апрель-июнь 625 г.) [+78] в Медину прибыли несколько представителей племени хузайма (входившего в союз ахабиш), сказавших, что племя приняло ислам, и они просят прислать наставников в вере [+79]. Мухаммад направил 6 или 10 человек, среди которых был Асим б. Сабит, отличившийся при Ухуде. Когда эта группа достигла ар-Раджи' (14 миль за ал-Усфаном), сопровождавшие ее хузаймиты изменили и призвали хузайлитов. Трое мусульман сдались, когда им обещали сохранить жизнь, а остальные пали с оружием в руках. Судьба сдавшихся оказалась более печальной: их повезли продавать мекканцам; один по дороге (в Марр аз-Захран) освободился от пут, схватил меч, но был забит камнями. Двое других были проданы мекканцам (потерявшим близких при Бадре), которые их убили (а одного и распяли). Вокруг этих первых мучеников ислама уже ко времени ал-Вакиди сложились легенды [+80].
В сафаре 4/13.VII-10.VIII 625 г. к Мухаммаду с той же просьбой обратился Амир б. Малик, один из глав племени амир б. са'са'а. К нему была послана группа в 14 человек. В дороге было получено какое-то настораживающее известие, и глава группы попросил у Мухаммада подкрепления. Вслед им были посланы еще 4 человека, в том числе Са'д б. Абу-л-Ваккас [+81]. Основная группа, полагаясь на гарантии, данные амиритами, безо всяких опасений прибыла в Бир Ма'уну, куда летом приводила на водопой свои стада часть бану сулайм. Среди сулаймитов оказался двоюродный брат Ту'аймы б. Ади, убитого при Бадре, жаждавший отомстить мусульманам. По его наущению сулаймиты напали на мусульман и перебили всех до одного. Са'д б. Абу-л-Ваккас и его спутники узнали об этом и возвратились в Медину.
Неудача всех этих акций показывает (несмотря на все недомолвки источников), что к Мухаммаду обращались лишь отдельные группы племен или возглавлявшие их лица, находившиеся в конфликте со своими сородичами и недостаточно сильные, чтобы обойтись без сторонней помощи. Мухаммад не упускал случая оказывать влияние через их посредство, но был достаточно дипломатичен и в обращении с противостоящей им стороной. Показательно, что когда возвращавшиеся из Бир Ма'уны под горячую руку убили двух человек из амир б. са'са'а (имевших гарантию безопасности от Мухаммада) и вождь этого племени, допустивший избиение мусульман в Бир Ма'уне, потребовал платы за кровь, то Мухаммад уплатил виру и возвратил трофеи, хотя, казалось бы, это убийство можно было расценить как ответ на нарушение гарантий безопасности со стороны амиритов. Такой жест Мухаммада подчеркивал его моральное превосходство над вождем, не выполнившим своего долга.
Со сбором средств для уплаты виры каким-то образом связан конфликт с бану надир, находившимся в союзнических отношениях с амир б. са'са'а, который кончился их изгнанием из Медины. До этого момента они соблюдали условия договора с Мухаммадом и не проявляли враждебности даже в тяжелый для него момент, когда мекканцы подошли к Медине. Это не исключало контактов отдельных лиц с мекканцами, которые могли рассматриваться как нелояльные. За такие связи был убит Ка'б б. ал-Ашраф, Абу Суфйан во время набега на Медину был гостеприимно принят одним из старейшин бану надир и получил от него необходимые сведения [+82], были, конечно, и другие случаи, оставшиеся неизвестными историкам.