The “distance effect” measuring the elasticity of trade flows to distance has been to be rising since the early 1970s in a host of studies based on the gravity model, leading observers to call it the “distance puzzle”. We review the evidence and explanations. Using an extensive data set of 124 countries over the period 1970-2005, we confirm the existence of this puzzle and identify that it only applies to poor countries (the bottom third in per capita income terms in our sample—i.e. the low-income countries according to the World Bank classification, 2006). We show that this group has intensified trade with closer partners and have 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, we estimate that low-income countries exhibit a significant rising distance effect on their trade around 18% between 1970 and 2006 while there is no more distance “puzzle” for trade within richer countries (the top third in per capita income terms in our sample). We dispose of several previous explanations of the puzzle, and note that this regionalization could well be a reflection of both increased integration of this group of countries in the world economy or a greater marginalization.