The links of the Arabs with the Persians go back well into Achaemenian times. According to Herodotus, iii. 5, Cambyses marched on Egypt via northern Arabia and the Hijāz after making a pact with and receiving a safe conduct from the king of the Arabs, probably to be identified with the ruler of Lihyān, predecessor of the Nabataeans in the region; and according to vii. 86–7, the Arabs furnished camel-mounted cavalrymen, who fought with bows, to Xerxes. The Arabs of north-western Arabia and the western fringes of the Syrian Desert passed under the suzerainty of Alexander the Great, according to Polybius and Pliny, and then under that of the Seleucids; thus the tradition was established, to endure down to the Muslim conquest of Syria in the 7th century A.D., of the Arabs acting as frontier auxiliaries for the Romans and then the Byzantines.

On the eastern fringes of the Syrian Desert, Arabs from the interior of the peninsula pressed into the fertile lands of Mesopotamia from an early date. The Assyrians had had a conscious policy of controlling the Arab tribes of northern Arabia, thereby curbing raids on caravan traffic across the peninsula, and they had made their authority felt as far west as Talmā’, occupied by Nabuna'id from 552 to 545 B.C. After the Persian capture of Babylon in 539 B.C., Cyrus the Great created a short-lived satrapy of ‘Arabāyā in northern Arabia, and Darius, seeking to encourage trade through the Persian Gulf, sent out the Greek Scylax of Caryanda on a voyage of exploration right round the coasts of the Arabian peninsula.