As the cost of air travel has decreased substantially in the USA and Europe over the past few decades, leisure travel to vacation destinations during the winter months has expanded significantly. This trend has probably increased the incidence of significant ultraviolet radiation exposure and sunburn in a broader population who could not previously afford this kind of travel. The purpose of this study was to analyse the correlation between increasing accessibility to air travel and melanoma incidence. This ecological study surveyed air travel patterns and melanoma incidence over the past three decades. Melanoma age-adjusted incidence was obtained from the United States Surveillance, Epidemiology, and End Results 9 Registry Database, 1975–2000, and the Cancer Registry of Norway, 1965–2000. United States mean inflation-adjusted airfare prices for four airports linked to leisure destinations (Miami, Los Angeles, San Diego, Phoenix) were compared with melanoma incidence. Parallel analyses were performed using annual domestic passenger-kilometres and melanoma incidence in Norway. Declining United States leisure-specific airfares corresponded strongly with increasing melanoma incidence (r=0.96, r2=0.92, P<0.001). Modelling a 5-year time lag between airfare and melanoma diagnosis strengthened the association (r=0.98, r2=0.96, P<0.001). Longer time lags could not be modelled due to data limitations. Data from Norway similarly showed that increasing air passenger mileage corresponded strongly with increasing melanoma incidence. Although correlation does not equate to causality, the very strong relationship between increasing access to air travel and melanoma incidence suggests that changes in recreational patterns may be contributing significantly to the public health problem of melanoma.