For centuries, incense moved from southern Arabia to the temples of Europe via the overland Incense Route. During the last century BC, the Himyarite people of southern Arabia began to secretly export incense to Nabataean ships from an island off their coast. They would float the incense out to the island using inflatable rafts made of animal skins. Then, out-of-sight from anyone observing from land, the Nabataean dhows would carry the incense up the Red Sea to Egyptian ports. In 25 BC the Himyarite people overthrew the other south Arabian kingdoms (with a little help from the Nabataeans who tricked the Roman army into fighting for them). (See South Arabia) Now the maritime incense trade flourished on the Red Sea.
An ancient shipping manual, 'The Periplus of the Erythraean
Sea' by an unknown author describes much of this trade. The principle
ports for incense trade were Cane, Aden and Muza in
the south, and Berinece, Philotera, Myos Hormos, Leuce Kome,
and Aila in the north. These ports had routes that led them to
Gaza and Alexandria.