It has been widely argued that, with the decline in trade costs, the importance of distance has declined over time. On the other hand, most gravity models find that the importance of distance on bilateral trade has increased over time. This puzzle is examined here. The paper develops a new measure of the distance of trade (dot) and shows that the dot falls over the period 1962-2000 for the average country in the world, with the number of countries with declining dot about double those with increasing dot. This implies an increased importance of distance over time. The paper argues that this result can be compatible with declining trade costs. Actually, we show that the decision about what proportion to trade at different distances does not depend on the level of trade costs but on the relative importance of its components. The paper also analyzes the impact on the dot of other determinants such as regional integration, changes in the geography of growth or in real exchange rates. Finally, the paper provides an empirical analysis of the evolution of the dot and explains most of its negative trend.