A modal shift to cycling has the potential to reduce carbon emissions in the transport sector. However, the carbon footprint of constructing new cycling routes, particularly greenways, has not been previously considered and has the potential to negate carbon savings of the modal shift of many commuters. This paper, using a case study of a greenway in Ireland, describes a methodology for calculating the carbon costs and savings associated with cycle route construction. By carrying out a life cycle assessment (LCA), the case study greenway was found to embody 67.6 tCO2e/km; the carbon savings of shifting one passenger kilometre travelled (PKT) from driving a car to cycling were found to average 134 gCO2e. In the case study, a shift of 115 commuters per year (253,000 PKT) is required to 'balance' or offset the carbon footprint of one 10 km asphalt greenway (assuming a 20 year life cycle). The methodology presented can be used to ensure the efficient and sustainable design of cycle networks internationally.