In this paper, we establish the importance of experience in international trade in reducing unmeasured trade costs and facilitating bilateral trade. We find a strong role for experience, measured in years of positive trade, for both aggregate and sectoral bilateral trade. In an augmented gravity framework, with a very comprehensive set of fixed effects and trend variables, we find that a 1% increase in experience at the country-pair level increases bilateral exports by 0.417% and reduces trade costs by 0.105%. Non-parametric estimates imply that nine years of experience is equivalent to a country pair joining a preferential trading area. We show that experience matters more for country pairs that are distant, non-contiguous, do not share a common language, lack colonial links and legal ties to one another. Subsequently, we construct microfounded measures of trade costs and show how these decline with the accumulation of experience. Our results are consistent with experience reducing the bilateral unmeasured variable costs of trade and experience shared across firms and industries.