We examine how uncertainty affects firms' internationalization choices. We begin by unveiling a new empirical regularity: using a unique dataset that allows us to study the dynamics of firms' exports and foreign direct investments (FDI) in individual destinations, we show that most firms serve a market via exports before investing there. To rationalize this pattern, we describe a model in which firms are uncertain about their profitability in a foreign market and may experiment via exports before engaging in FDI. In line with this idea, we show that the probability that a firm starts investing in a foreign country increases with its export experience in that country. In more uncertain destinations, firms delay FDI entry, experimenting longer with exports before establishing foreign affiliates.