As the main link of international trade, logistics plays a pivotal role in the entire international trade transactions, and choosing the appropriate logistics path is conducive to cost savings for enterprises. This study combines the traditional logistics model with the actual situation of international trade to select the headway transportation, overseas warehouses and tail distribution as the main elements of enterprise logistics cost optimization in international trade. Based on the cost calculation of the main elements, we design the objective function and constraints of enterprise logistics cost optimization, build the optimization model, and obtain the optimal solution by iterative analysis using the fitness function and genetic operator in genetic algorithm. The empirical analysis shows that after applying the optimization model, the total logistics cost of enterprise D is reduced from US$99,373,500 to US$72,653,400, indicating that the model is effective in optimizing the logistics cost of enterprise D in international trade. This study provides an effective method for the optimization of cross-border enterprise logistics costs, which has a positive role in promoting the development of international trade.