A rigorous model to quantify the carbon footprint of FL is proposed, hence facilitating the investigation of the relationship between FL design and carbon emissions, and an early-stage FL optimization problem is formalized enabling the community to consider the importance of optimizing the rate of CO2 emissions jointly to the accuracy of neural networks. Despite impressive results, deep learning-based technologies also raise severe privacy and environmental concerns induced by the training procedure often conducted in data centers. In response, alternatives to centralized training such as Federated Learning (FL) have emerged. Perhaps unexpectedly, FL in particular is starting to be deployed at a global scale by companies that must adhere to new legal demands and policies originating from governments and the civil society for privacy protection. However, the potential environmental impact related to FL remains unclear and unexplored. This paper offers the first-ever systematic study of the carbon footprint of FL. First, we propose a rigorous model to quantify the carbon footprint, hence facilitating the investigation of the relationship between FL design and carbon emissions. Then, we compare the carbon footprint of FL to traditional centralized learning. We also formalize an early-stage FL optimization problem enabling the community to consider the importance of optimizing the rate of CO2 emissions jointly to the accuracy of neural networks. Finally, we highlight and connect the reported results to the future challenges and trends in FL to reduce its environmental impact, including algorithms efficiency, hardware capabilities, and stronger industry transparency.