Due to their authentic urban and architectural character, the Medinas of Tunis and Marrakesh became listed among the United Nations educational, scientific, and cultural organization (UNESCO) heritage sites in 1979 and 1985, respectively. Nowadays, the urbanization of the surrounding green areas and the climate change impacts on cities are degrading the Medinas’ livability and their characteristic heritage. On the other hand, scientific knowledge and data about the green system in the dense urban cores of Medinas in the Maghreb region is still not a widely apprehended theme in the scientific domain. This research objective is to initiate nature-based and sustainable solutions in these cities by demonstrating the application of the urban green infrastructure (UGI) approach. As a research methodology, an analysis of the historical green system development in the Medinas is given to highlight their tangible and intangible values. The analysis goes over three periods: first, the medieval Islamic era, then the modern period during the French colony, and the contemporary city as a unique urban landscape. Finally, the study proposes a design guideline to prove the applicability of the UGI in the given historical morphologies by implementing the retained historical values of the historic green heritage in Medinas and the aspects of the site.