The fleet assignment problem is to determine an optimal assignment of aircraft types to flight legs in a specified flight network. The assignment process must trade off the operating costs of large capacity aircraft with the lower operating costs, but potentially large amount of lost revenue, associated with small capacity aircraft. In this thesis, we investigate the relationship between this trade-off and the multi-leg nature of passenger itineraries. We detail limitations of the current fleet assignment practices. In an attempt to alleviate these limitations, we present a new paradigm for fleet assignment that better estimates the quantity of revenue lost (called spill costs) when inadequate capacity is assigned to flight legs. Our paradigm also includes a procedure that allows a basis of comparison for different assignments. We develop a deterministic linear program that routes passengers over a flight network which is the first to include the partial recapture of passengers. This model has a variety of uses in other airline decision processes including recovery operations, revenue management, and the fleet assignment problem. To estimate spill costs, airlines typically pro-rate multi-leg passenger fares based on the flying miles of each flight leg in the itinerary. We present different spill models, coupled with various fare allocation schemes, that can yield better fleeting decisions. Using data from a major U.S. airline, we calculate that the annual savings from our approach are on the order of $30M. We combine the fleet assignment model and the passenger mix model and show that our models result in near optimal fleetings. In fact, there are special conditions when the optimal solution of the conventional fleet assignment model is also the optimal solution for this combined model. Finally, we present evidence that suggests that capturing the network effects of multileg passenger itineraries is as important as capturing the stochastic nature of airline passenger demand in the fleet assignment model.