In recent years European cycling has undergone a renaissance with various initiatives including the establishment of EuroVelo and the proposed European trans-border cycling infrastructure. Significant advances on this infrastructure have been made with 45,000 km of bike paths completed. In Ireland, to encourage a modal shift among commuters to cycling, and help boost facilities for leisure cyclists and cycle tourism, the Irish Government has proposed the establishment of a 2,000 km National Cycle Network (NCN). The NCN will be modelled on international networks such as the Vias Verdes (Spain), Landelijk Fietsroutes (Netherlands) and D-Netz (Germany) and the Sustrans NCN (UK). It will comprise a range of cycle route types including: (i) on-road, (ii) cycle lanes, and (iii) greenways (traffic-free cycle trails). While a modal shift to cycling has clear potential to reduce carbon emissions in the transport sector the climate cost of constructing new cycling routes, particularly greenways, has not been previously considered. Carbon emissions during rural cycle lane construction, have the potential to negate the carbon savings made by the modal shift of many commuters. This paper, using a case study, describes a methodology for calculating the potential carbon emissions associated with cycle lane construction. It was found that the embodied carbon of on-road cycle routes and cycle lanes were generally not significant. On the other hand, the case study greenway was found to embody 60.4 tCO2e/km. The carbon savings of shifting a Passenger Kilometre Travelled (PKT) from driving a car to cycling were found, in Ireland, to average 134 gCO2e/PKT. Therefore, in the example presented, a shift of 102 commuters per year (224,400 PKT) are required to offset the carbon footprint of one 10 km asphalt greenway. The metric presented can (i) be used, at design stage to compare proposed routes in terms of their embodied carbon and (ii) be integrated in a wider design matrix to ensure the efficient and sustainable design of cycle networks internationally. This research was commissioned through the National Roads Authority (Ireland) Research Programme and is funded by the National Sustainable Transport Office at the Department of Transport, Tourism and Sport (Ireland) and the College of Engineering and Informatics at NUI Galway.