This paper describes a new methodology for quantifying the environmental emissions and cost savings associated with the implementation of a telemedicine service. The methodology has been applied to the Health Department of Alcoy, Alicante (Spain). The amounts saved in different implementation scenarios were obtained, and scenarios were compared. The proposed quantification methodology is based on a combined flow of operations and calculus with data obtained from public and official sources. The methodology allows obtaining savings for different parameters (such as distance, time, liters of fuel, or kg of atmospheric pollutants emitted). Moreover, it enables the quantification of the parameters for different implementation scenarios, providing an objective description of different service operation alternatives. In this paper, the methodology is applied to the Alcoy Health Department (Spain) and five scenarios for the implementation of a telemedicine service are analyzed and compared. The results obtained with the proposed methodology are consistent with those published in previous studies. This supports its use in evaluating environmental costs and in selecting alternatives for the implementation of new telemedicine services. The methodology can be extrapolated to the characterization of a health department worldwide. It is therefore presented as a free, sustainable tool that calculates data that are fundamental for use in decision-making processes from an environmental point of view. In the Health Department of Alcoy, it was obtained a reduction in costs and emissions of 25% when raising 50% of follow-on visits via telecare. Withal each increase of 10% of follow-on visits telecare carried entails increasing environmental savings by up to 5%.