There has been Incense Trade Route for as long as there has been recorded history. As soon as the camel was domesticated, Arab tribes began carrying incense from southern Arabia to the civilizations scattered around the Mediterranean Sea. Up until 24 BC the Nabataeans moved large caravans of frankincense, myrrh and other incenses from southern Arabia and spices from India and beyond to the Mediterranean ports of Gaza and Alexandria. The Roman historian Pliny the Elder mentioned that the route took 62 days to traverse from one end to the other. Many of the route stops were cities or towns while others were simply watering locations or dry encampments in the desert.
It is important to note that the Incense Route was not fixed. As towns or kingdoms tried taxing the caravans passing through them, the merchants would switch their routes, using different passes or treks through the desert. As a result, towns along the route would wax and wane, depending on the route that the caravans took.
Soon after 24 BC, the Incense Road began to be replaced by the Incense Sea Route.

Information source: UNESCO World Heritage web site