This paper has been motivated by a fleet optimization problem faced by one of the leading European cargo rail companies. The company operates a fleet of more than 100,000 rail cars and annually invests significant sums of money into new cars. Because the price tag of a new car is over 50,000 euros, planning such a fleet is an important activity at the company. In this paper, we develop and solve analytical models for fleet planning. We first describe the rental process and show how it can be modeled as a queuing loss system. We then develop a profit function and derive several structural results, such as the concavity of the profit function in the fleet size. Building on these structural results, we show how the fleet size can be optimized, how the fleet structure (i.e., the types of cars being used) can be optimized, and how a joint fleet of owned and leased cars can be optimized. Because some of the optimal methods are difficult to implement, we also develop and test an approximation that is easy to implement. To illustrate our findings and to validate our approach, we provide numerical results that are based on data of the company that motivated our research.