Boosting building renovation is urgently needed to achieve carbon neutrality by 2050. Building retrofit can be achieved by energy-efficient measures such as thermal insulation or replacement of a fossil heating system. Currently, conventional materials that are mostly used for envelope insulation raising the risk of a lock-in situation where measures to mitigate climate change are actually contributing to it. Bio-based materials are a promising alternative as they can be used to not only reduce the energy consumption of a building but also temporarily store carbon. To evaluate the potential benefits of such materials, life cycle assessment (LCA) and life cycle cost analysis (LCCA) are commonly used. Such assessment allows the analysis of a building over its whole life. However, considering that buildings are very long lasting systems, many associated uncertainties can affect the outcome of LCA and LCCA. To account for all the uncertainty sources and provide a robust solution for building renovation, uncertainty quantification can be applied. In this paper, we use robust optimization under uncertainties to define the most cost-effective and climate-friendly solution. We apply bio-based materials and include carbon storage calculation in the integrated LCA and LCCA. For the robust optimization, we use a novel methodology combining a well-known non-dominated sorting genetic algorithm II (NSGA-II) with surrogate modeling to lower computational cost. The methodology is applied for a case study located in Switzerland. The results show that bio-based materials provide a robust solution for building renovation but to achieve the highest reduction potential, bio-based envelope insulation should be combined with the replacement of the existing fossil heating system.