The "distance effect" measuring the elasticity of trade flows to distance has been rising since the early 1970s in a host of studies based on the gravity model, leading observers to call it the "distance puzzle". This paper reviews the evidence and explanations. Using an extensive data set of 124 countries over the period 1970-2005, the authors confirm the existence of this puzzle and identify that it only applies to poor countries (the bottom third in per capita income terms in the sample -- i.e., the low-income countries according to the World Bank classification, 2006). The analysis shows that this group has intensified trade with closer partners and has chosen new partners that are closer than existing partners, leading to a regionalization of their trade at both extensive and intensive margins (regionalization of trade is absent for the other countries). Combining several methods on cross-section and panel estimates of the gravity equation, the authors estimate that low-income countries exhibit a significant rising distance effect on their trade, around 18 percent between 1970 and 2006. There is no more distance "puzzle" for trade within richer countries (the top third in per capita income terms in the sample). The paper disposes of several previous explanations of the puzzle, and notes that this regionalization could well be a reflection of increased integration of this group of countries in the world economy or greater marginalization.