Regular aerobic exercise is recommended by physicians to improve health and longevity. However, individuals exercising in urban regions are often in contact with air pollution, which includes particles and gases associated with respiratory disease and cancer. We describe the recent evidence on the cardiovascular effects of air pollution, and the implications of exercising in polluted environments, with a view to informing clinicians and other health professionals. There is now strong evidence that fine and ultra fine particulate matter present in air pollution increases cardiovascular morbidity and mortality. The main mechanisms of disease appear to be related to an increase in the pathogenic processes associated with atherosclerosis. People exercising in environments pervaded by air contaminants are probably at increased risk, due to an exercise-induced amplification in respiratory uptake, lung deposition and toxicity of inhaled pollutants. We make evidence-based recommendations for minimizing exposure to air-borne toxins while exercising, and suggest that this advice be passed on to patients where appropriate.