Building energy renovation is urgent in order to lower green house gas (GHG) emissions and achieve carbon neutrality by 2050. Building energy renovation can be achieved by more efficient thermal insulation and replacing the fossil heating system in a building. Currently, conventional building insulation materials dominate the market. However, to drastically reduce GHG emissions, bio-based materials are a valuable asset. These can be applied not only to reduce the operational energy but also to temporarily store carbon in the building stock. To evaluate the environmental and cost performance of such insulation, life cycle cost analysis (LCCA) and environmental life cycle assessment (LCA) can be used. However, as buildings are long lasting systems, many parameters in these analyses are uncertain. Such parameters include the future climate, future inflation rates, point in time when materials are replaced, future energy policies, and so on. In this paper, we apply bio-based insulation materials for building renovation and define the optimal solution for building energy-related renovation using a novel methodology, which combines non-dominated sorting genetic algorithm (NSGA-II) with surrogate modeling. We use materials such as straw, hemp, and wood fibre along with conventional materials such as EPS. At the same time, we account for the uncertainties associated with these materials’ production and replacement as well as those associated with the future building operation. In this analysis, we also include the carbon storage calculation. The results show that bio-based materials provide a robust solution for building renovation and have high potential to store carbon in building components in comparison with conventional insulation materials. The results also show that to achieve the highest GHG emissions reduction, building energy-efficient measures should be combined with the replacement of the existing fossil heating system. The approach presented here allows the identification of the robust and optimal building renovation solution performed with bio-based materials and the comparison of such renovation with conventional materials.