This paper contributes to the development of an eco-friendly composite cementitious material using local resources from southeastern Algeria, a Saharian region characterized by an arid climate with scorching summers and severe winters. To address these climatic and environmental challenges, the conventionally used alluvial sand (AS) and quarry gravel were substituted with Saharan dune sand (DS) and crushed desert rose (CDR), a local stone historically utilized in traditional Saharan construction. The desert rose was crushed and graded into two particle sizes (3/8 mm and 8/15 mm), while the dune sand was incorporated into the alluvial sand at varying substitution rates (0%, 10%, 20%, 40%, and 50%). A concrete mix design was developed based on these two aggregates and used to manufacture solid bricks measuring (4x10x16 cm). Experimental results indicate that the optimal formulation, consisting of 40% dune sand (DS) combined with crushed desert rose (CDR), exhibited highly promising physical, mechanical, and thermal properties. Consequently, this sustainable material offers a superior alternative to traditional raw materials. Furthermore, it provides a resilient solution to climate change compared to modern industrial materials, thereby preserving local thermal comfort as well as the unique architectural and historical heritage of the region.