In the Libyan Desert, the Gilf el-Kebir and Jebel el-'Uweināt are two large rock formations located in the extreme South-West of Egypt, at the edge of the Libyan and Sudanese borders. A hundred and twenty kilometers from each other, they are surrounded by plains and sandy formations, punctuated by a few smaller massifs. Although they are of different ages and geological formations, the two great massifs both offered interesting and complementary refuges for prehistoric groups who used rock shelters, cliffs and boulders for engraving and painting. The existence of a multitude of styles and techniques allow to detect striking parallels between the rock art record of the two regions, providing a dynamic view of the regionalization of rock art and of how these territories were conceived and occupied by semi-nomadic groups during the Holocene optimum period (8000–3500 BCE). Paintings from the Gilf el-Kebir show very close stylistic affinities with representations identified in the Jebel el-'Uweināt. But the fact that they remain a minority in the overall rock art record from both areas tends to evidence that, contrary to what has been hypothesized before, migrations between the Gilf el-Kebir and the Jebel el-'Uweināt were not systematic. This paper also highlights a possible increase in the contacts and migrations between the two massifs after the adoption of pastoralist lifestyles. The repartition of rock art and the evolution through times of the parallels offers interesting insights into land use strategies of both hunter-gatherers and herd keepers in such contrasted environments, and into what can be called symbolic territories.