Transport has a large number of significant externalities including carbon emissions, air and noise pollution and congestion. Active modes of travel such as cycling and walking can reduce these externalities. Moreover, public health research has identified large additional social gains from active travel: health benefits of increased physical exercise. We introduce such a health benefit to a model of transport externalities in order to study appropriate policy responses. When physical exercise is considered welfare-enhancing, the optimal gasoline tax increases. However, it increases by less than the proportional increase in the social cost per mile travelled in private vehicles because physical activity is mediated by the ratio of the cross-price elasticity of active travel with respect to fuel price, and the fuel price elasticity. Under our central assumptions, the optimal fuel tax increases by 28% in the UK and 60% in the US when health benefits from physical exercise are included. We argue that fuel taxes should be implemented jointly with other policies aimed at increasing the uptake of active travel.