Достаточно успешной была иудейская проповедь и в центральной, и в северной части Аравийского полуострова. Иудейские колонии имелись во многих оазисах Хиджаза и Неджда. На севере от Мекки были поселения многочисленных иудейских племен. Вокруг города Ясриб находились три иудейских поселения. Скорее всего, это были арабы, обращенные в иудаизм. Среди иудеев Аравии в то время получили широкую известность мессианские идеи, связанные с ожиданием прихода мессии.
С IV в. арабы подвергались пристальному вниманию христианских миссионеров — сирийцев, эфиопов, в меньшей степени греков.
Монофизиты постоянно стремились к обращению бедуинов, в большие становища они назначали епископов. Несториане также вели широкую миссионерскую деятельность: с V века в Хире существовала несторианская епархия. В 410 г. в Хире был основан монастырь и рукоположен епископ. Князь Аль-Мундир III (ум. 554) имел жену-христианку, некоторые из его знати также были христианами. Епископы появлялись в Омане в 424-м и, в районе Бахрейна, в 575-м гг., из этих границ христианство распространялось вовне. Имелись епископы в Айле, Думе и Тайме, и большинство племен Севера имело некоторое знание христианства. Последний правитель Лахмидского государства принял христианство. Ближе к югу Аравии возник город Наджран — христианский центр, основанный миссионером-несторианином Фамийуном, обратившим людей этого региона в христианство.
Известно, что северное арабское письмо, которым был записан и Коран, было создано христианскими миссионерами из Хиры за столетие до появления ислама. Первые северноарабские надписи были найдены на церковных вратах в Забаде в Сирии (512 г), а другие в Харране (568 г).
Характерный пример из истории православной миссии — в 450 г. св. Евфимий крестил Ассаба Эль-Беита, вождя бедуинского племени, вместе с его сыном, исцеленным по молитвам святого. Вскоре новокрещеный вождь по имени Петр привел ко крещению все свое племя. Через какое-то время он был рукоположен Иерусалимским патриархом в епископа Бедуинского, потому что епархия не имела никакого города или определенной местности пустыни. От племени Петра христианство было распространено к другим соседним племенам.
Литургия совершалась в передвижных храмах, которые устанавливались на местах новых кочевок, алтари делались из овечьей шкуры, епископы, в виду условий пустыни, дозволяли перед Причастием пить воду.
Из житий святых подвижников, уходивших для подвигов в аравийские пустыни, мы знаем, что такой пример святости нередко приводил к массовым обращениям соседствующих арабов. Более того, среди почитаемых Церковью святых, имеются арабы V–VI вв., напр. прп. Юлиан Слепец или св. Илия Араб (415–494) из Неджда. Надписи VI в. показывают, что в церковный обиход уже в то время входил и арабский язык. Среди доисламских поэтов были и арабы-христиане — Ади ибн Зайд, Барака б. Науфаль. Есть даже мнение, что первый арабский перевод Библии появился в районе Хиры около 620 года, но в настоящее время оно не разделяется большинством ученых.