Abstract Background Previous studies have demonstrated links between cardiovascular disease and physical inactivity and poor air quality, which are both associated with neighborhood greenness. However, no studies have directly investigated neighborhood greenness in relation to coronary heart disease risk. We investigated the effect of neighborhood greenness on both self-reported and hospital admissions of coronary heart disease or stroke, accounting for ambient air quality, socio-demographic, behavioral and biological factors. Method Cross-sectional study of 11,404 adults obtained from a population representative sample for the period 2003–2009 in Perth, Western Australia. Neighborhood greenness was ascertained for a 1600 m service area surrounding the residential address using the mean and standard deviation of the Normalized Difference Vegetation Index (NDVI) obtained from remote sensing. Logistic regression was used to assess associations with medically diagnosed and hospitalization for coronary heart disease or stroke. Results The odds of hospitalization for heart disease or stroke was 37% (95% CI: 8%, 57%) lower among adults in neighborhoods with highly variable greenness (highest tertile) compared to those in predominantly green, or predominantly non-green neighborhoods (lowest tertile). This effect was independent of the absolute levels of neighborhood greenness. There was weaker evidence for associations with the mean level of neighborhood greenness. Conclusion Variability in neighborhood greenness is a single metric that encapsulates two potential promoters of physical activity - an aesthetically pleasing natural environment and access to urban destinations. Variability in greenness within a neighborhood was negatively associated with coronary heart disease and stroke.