Making sustainable conceptual design decisions is the key to reduce the environmental impact of the construction industry. Such early decisions, which must be given in a short timeframe, have the largest impact on a project’s quality, cost and embodied carbon. This study showed how much the conceptual design decisions affect the cost and carbon footprint of a building’s structure using our Non-dominated Sorted Genetic Algorithm II tool. First, we tested the tool’s reliability by comparing its solutions with three case studies from literature. Then, we showed that by quickly examining various conceptual design solutions on a Pareto graph (which spotlights cost and CO2-optimized options), more sustainable design alternatives can be identified. Then, using the tool, we analyzed 36 building configurations, providing a spectrum of embodied carbon emissions (including the life cycle assessment steps A1, A2, A3, A4, A5, C2, C3, C4) ranging between 60 and 360 kgCO2e/m2. By comparing 25 material types from 15 databases (EPDs and ICE), we concluded that the geometry decisions (span length, height and shape) have the largest influence, material type (steel, timber, reinforced concrete), recycling and reuse of steel are crucial, and the embodied carbon calculations are highly sensitive to the supplier data and location. Overall, this study showed that architects and engineers possess the ability to significantly reduce the embodied carbon of structural systems by selecting the appropriate materials and structural system at the conceptual design stage.