During the last two decades, two important contributions have reshaped our understanding of international trade. First, countries trade more with those with whom they share history, language, and culture, suggesting that trade is limited by information frictions. Second, countries are more likely to start exporting products that are related to their current exports, suggesting that shared capabilities and knowledge diffusion constrain export diversification. Here, we join both of these streams of literature by developing three measures of bilateral relatedness and using them to ask whether the destinations to which a country will increase its exports of a product are predicted by these forms of relatedness. The first form is product relatedness, and asks whether a country already exports many similar products to a destination. The second is importer relatedness, and asks whether the country exports the same product to the neighbors of the target destination. The third is exporter relatedness, and asks whether a country’s neighbors are already exporting the same product to the destination. We use bilateral trade data from 2000 to 2015, and a variety of controls in multiple gravity specifications, to show that countries are more likely to increase their exports of a product to a destination when they have more product relatedness, importer relatedness, and exporter relatedness. Then, we use several sample splits to explore whether the effects of these forms of relatedness are stronger for products of higher complexity, technological sophistication, and differentiation. We find that, in the case of product relatedness, the effects are stronger for differentiated, complex, and technologically sophisticated products. Also, we find the effects of common language and shared colonial past to increase with differentiation, complexity, and technological sophistication, while the effects of shared borders decrease with these three variables. These results suggest that product relatedness and common language capture dimensions of knowledge relatedness that are more important for the exchange of more sophisticated and differentiated products. These findings extend the ideas of relatedness to bilateral trade and show that the evolution of bilateral trade networks are shaped by relatedness among products, exporters, and importers.