Z momentem przyłączenia Egiptu do Imperium Rzymskiego w 30 r. p.n.e., Oktawian August dostrzegł szereg problemów, które wiążą się z nową prowincją. Od południa rozpoczęły się regularne najazdy Kuszytów, a od strony Morza Czerwonego czaili się arabscy piraci. Dodatkowo wskutek dominacji handlowej Himjarytów i Sabejczyków w cieśninie Bab el Manbed, Rzymianie mieli utrudnioną możliwość rejsu na tym ważnym szlaku do Indii.
Władze rzymskie nie mogły sobie pozwolić na bagatelizowanie zagrożenia, dlatego nowy prefekt Egiptu, G. Emiliusz Gallus zdecydował się na przeprowadzenie ryzykownej i niespotykanej jak dotąd w rzymskiej historii, wyprawy do Arabii Felix, aby zakończyć dominację handlową Arabów na Morzu Czerwonym. Gallus zebrał w porcie w Kleopatris kontyngenty złożone 10 000 rzymskich legionistów stacjonujących w Egipcie, 500 Żydów oraz 1 000 Nabatejczyków z Petry, którymi dowodził Syllaeus.
Wyprawa wojskowa wypłynęła w 25 r. p.n.e. z Kleopatris na południe, lecz w wyniku licznych problemów i straty wielu statków, flota Gallusa musiała przybić do lądu w porcie Leuke Kome (w pobliżu El Haura). Gallus spędził następnie tam całe lato i zimę, poprzednio planował dopłynąć statkami na południe Arabii, lecz wskutek straty okrętów rejs był niemożliwy, co wymusiło na nim podjęcie decyzji o kontynuowaniu reszty trasy lądem.
Z początku 24 p.n.e. rzymskie wojsko skierowało się na południe, wykorzystując wielbłądy do transportu wody. Rzymianie wędrowali wiele dni po bezludnej pustyni. Po męczącej trasie piaskowymi bezdrożami Gallus dotarł do nawodnionej i żyznej krainy Negrany (prawdopodobnie dziś. Nedżran), gdzie rozpoczął oblegać jej miasto. Rzymianie przeprowadzili szturm i zdobyli miasto. Rzymskie wojska dotarły następnie nad pewną rzekę, gdzie zastąpiły im drogę wojska arabskie. Gallus odniósł wielkie zwycięstwo w bitwie, zabijając 10 000 arabskich wojowników, a tracąc po swojej stronie zaledwie kilku, ponieważ przeciwnik był bardzo słabo uzbrojony. Arabscy wojownicy nie zdawali sobie sprawy o wysokim poziomie militarnym rzymskiego wojska.
Gallus opanował następnie dwa ważne ośrodki handlowe o nazwie Asca i Athrula, gdzie zbudował magazyny, aby przechowywać w nich zaopatrzenie i założył rzymski garnizon. Wojska rzymskie skierowały się następnie do kraju plemienia Rammanitów, którzy pod wodzą króla Ilisarosa, skryli się w swojej stolicy Marsiaby (dziś. Mar’ib). Gallus zaczął oblegać miasto, lecz wskutek braku wody, musiał po 6 dniach odstąpić od blokady. W marcu, gdy Gallus przebywał w kraju Rammanitów, doniesiono mu, że znajduje się zaledwie dwa dni drogi od wspaniałej krainy pachnideł, czyli Hadramautu. Gallus postanowił tam wyruszyć, ponieważ spodziewał się, że właśnie tam znajdują się siedziby Sabejczyków i Himjarytów. Zamiast jednak osiągnąć południowe wybrzeże Arabii, błądził 6 miesięcy po pustyni wskutek zdradliwości przewodników i Syllaeusa. Ostatecznie zrezygnował z trasy i powrócił do Negrany. Gallus zrezygnował ostatecznie z dalszej wyprawy na południe i pomaszerował na północ, przez miasto Hepta Phreatae – „Siedem Źródeł”, docierając ostatecznie do wsi Egra nad Morzem Czerwonym. Tam przerzucił swoje zmęczone i przetrzebione wojska na nowo zbudowane statki, którymi dopłynął do Myos Hormos w Egipcie, docierając ostatecznie pod koniec 24 r. p.n.e. do Aleksandrii.
Ekspedycja Gallusa nie wpłynęła na ograniczenie monopolu handlowego Himjarytów i Sabejczyków, ponieważ wskutek słabej znajomości wnętrza Arabii, nie potrafił dobrze zlokalizować swojego położenia. W wyniku tego posiadłości arabskich kupców na wybrzeżu, głównie miasto Aden (zniszczone przez Rzymian w 1 r. p.n.e.), nie zostały zdobyte, a dominacja Sabejczyków i Himjarytów wciąż trwała. Była to jednak najbardziej śmiała wyprawa rzymskich wojsk na półwyspie arabskim, która umożliwiła lepsze poznanie pustynnych terenów po drugiej stronie Morza Czerwonego.
