Given the increasing role of transportation in modern societies, an efficient transportation fleet has become a critical factor in enhancing the performance of distribution systems. Effective fleet management directly impacts costs, transit times, reliability, flexibility, safety, and the environment. Consequently, optimal fleet sizing in organizations that heavily depend on transportation is essential for cost control and reduction. This study proposes a model for optimal fleet sizing in a multi-modal automotive distribution system, considering uncertainties in demand and travel time. The problem is formulated with the objective of minimizing total costs, including purchasing, hiring, operating, and maintenance expenses, and is developed under real-world constraints and conditions. The model considers not only the purchase of trailers and car carriers but also the possibility of entering into short-term and long-term hire agreements. Results for the studied company indicate that the maximum purchase budget is used to provide owned fleets. Moreover, implementing the proposed model could reduce the company’s total purchasing, hiring, operating, and maintenance costs by approximately 21.34% compared to current practices.