Bilateral trade balances often play an important role in the international trade policy debate. Disturbingly, several studies argue that the gravity model of trade fails when confronted with bilateral trade balances data, dubbing this "The Mystery of the Excess Trade Balances". Capitalizing on developments in the related literature, we solve the mystery and show that the gravity model explains bilateral trade balances well. We also uncover a new property of the structural multilateral resistances as asymmetric trade costs. This is exactly what solves the mystery. Our analysis suggests that, on average, there is little room for trade cost asymmetries due to 'unfair' policies to lead to bilateral trade imbalances. However, we also identify sectors (e.g., Mining and Services), where the modeling of the direct bilateral trade costs in the gravity model can be improved, including the possibility for 'unfair'/asymmetric policies to play a more significant role.