Previous studies have demonstrated a modest association between smoking and leukemia particularly for myeloid disorders. Our objective was to examine whether changing trends in cigarette smoking prevalence nationally and within selected states parallel similar trends in mortality from leukemia. Trends in national smoking rates were correlated with trends in leukemia mortality rates obtained from the Centers for Disease Control and Prevention and the Surveillance Epidemiology and End Results registry, respectively. State-specific correlations were assessed from 1984 to 2004 using smoking prevalence data from the Behavioral Risk Factor Surveillance System and leukemia mortality data from National Vital Statistics System. Correlations were computed using the Spearman rank correlation coefficient. Leukemia mortality decreased overall in the United States in parallel with decreased smoking. Analyzed on a state-specific basis, leukemia mortality decreased in states where smoking rates declined markedly but remained unchanged where smoking prevalences were relatively stable. The findings suggest that declining rates of leukemia mortality are associated with changing patterns of smoking behavior.