Despite the strong pace of globalisation, the distance effect on trade is persistent or even growing over time (Disdier and Head, 2008). To solve this distance puzzle, we use the recently developed gravity equation estimator from Helpman et al. (2008) (HMR henceforth). Using three different data sets, we find that the distance coefficient increases over time when ordinary least squares (OLS) is used, while the non‐linear estimation of HMR leads to a decline in the distance coefficient over time. The distance puzzle, thus, arises from a growing bias of OLS estimates. The latter is explained by an increase in the importance of the bias from omitting the number of heterogeneous exporting firms relative to the bias from omitting zero trade flows. Furthermore, we show that including zero trade flows cannot solve the distance puzzle when using HMR. The HMR estimates are strongly correlated with the time pattern in freight costs reported by Hummels (2007).