The rapid growth of the cloud computing market is driving a significant increase in power consumption and the related carbon footprint. At the same time, the heating sector is a major contributor to global energy-related carbon emissions. Since cloud infrastructures convert almost all of the electricity they consume into heat, harnessing this excess heat offers tremendous opportunities for decarbonization. However, implementation in practice is still rare and there is a lack of studies that integrate these strategies into network planning and cost-benefit assessment. Hence, we propose a bi-objective mixed-integer programming model for the network design of cloud infrastructures that incorporates the option of excess heat utilization, renewable energy integration, and energy efficiency considerations while minimizing total cost and carbon emissions. Strategic decisions include multi-period site decisions for cloud infrastructure, renewable energy capacity, and integration with district heating networks. Operational decisions include the provision of computing resources, energy supply, and heat utilization on a seasonal scale. Through a comprehensive case study, we demonstrate the optimal design of a cloud infrastructure network in Europe over the next decade. Remarkably, our approach indicates the potential for a net reduction of 4.4 million tonnes of carbon emissions at minimal cost of €70.3 billion, with a total excess heat utilization of 381.7 terawatt-hours. In addition, our results provide valuable insights for industry and policy makers to enable economic and sustainable design of cloud infrastructures with excess heat utilization.