This study examines the impacts of distance factors on Mainland Chinese tourists’ international destination choices in 2007 and 2015 and how these factors’ effects change over time. A random-coefficients conditional logit model was utilized to investigate three types of destination choices: past destination choice, dream destination choice, and intended destination choice. We identified different effects of distance factors on these different types of destination choices. Our results reveal substantial heterogeneity in the effect of cultural distance; in most cases, positive and negative effects of cultural distance co-occurred among Chinese residents. In comparing estimates from different years, we found diminishing effects of geographic distance on dream and intended destination choices. Theoretical and practical implications are discussed.