Research has tackled the physical expansion of urban growth and concomitant rural-urban transformation of land use in many parts of the world, but this phenomenon remained largely overlooked in the Middle East and North Africa (MENA) region. To fill this knowledge gap, this study investigated land use changes from the 1970s to 2018 in the cities of Luxor and Cairo in Egypt, and of Aqaba and Amman in Jordan using different Landsat datasets. Land cover classifications were performed using the Maximum Likelihood Algorithm and Spectral Angle Mapper. In all four cities peri-urban green areas shrunk or shifted due to increased expansion of built-up areas. The largest reductions of peri-urban green areas were observed for Amman and Luxor, which decreased by 122.4 km2 and 17.2 km2, respectively, over the study period. For Cairo, an increase of peri-urban green area by 29 km2 was detected, but its location shifted over the last five decades due to urban expansion. In 2018, green areas (urban and peri-urban) on a per-capita basis were 4.6, 12, 91, and 142 m2/capita for Aqaba, Cairo, Amman, and Luxor, respectively. Land cover changes reflected critical political events like the so-called “Arab Spring”, international treaties, recent migration waves and population growth. Rapid increases in urban built-up area put pressure on scarce land and water resources in the peri-urban fringes, thereby potentially leading to environmental stress. Effective city planning is needed to address the multiple challenges and competing interests of urban and peri-urban environments.