The construction industry is a major contributor to global carbon emissions, emphasizing the need for sustainable material choices to mitigate environmental impacts. This study evaluates the energy efficiency and carbon footprint of natural stones used as exterior wall cladding in buildings situated in the Afyon region, Turkiye. Nine different natural stones—Afyon Kaymak, Milas Leylak-I, Milas Leylak-II, Milas Leylak-III, Traverten-I, Traverten-II, Teos Yeşil, Yaylak Granite, and Dune Granite—were analyzed based on their technical properties and thermal performance. To quantify the environmental impact, annual energy consumption and CO2 emissions of a sample building were assessed using IES-VE software under Afyon’s climatic conditions. Three different wall configurations (sandwich wall, externally insulated, and internally insulated), two primary wall materials (aerated concrete and pumice concrete), and expanded polystyrene (EPS) insulation were considered, leading to 54 alternative scenarios. The results revealed the most energy-efficient natural stone alternative with the lowest CO2 emissions, providing significant implications for sustainable building practices. Moreover, regression and sensitivity analyses were conducted to determine the influence of various parameters on energy consumption and carbon emissions. The findings underscore the potential of natural stone cladding in reducing the environmental footprint of construction materials, offering practical insights for architects, engineers, and policymakers striving for sustainable and low-emission buildings. This study contributes to the advancement of eco-friendly construction by identifying optimal material choices that enhance both energy efficiency and environmental sustainability.