This paper presents a new tabu search based two-dimensional bin packing algorithm which produces high quality solutions to the Mixed Payload Airlift Load Planning (MPALP) problem using C-5 and C-17 aircraft. This algorithm, called Mixed Payload Airlift Load Planning Tabu Search (MPALPTS), surpasses previous research conducted in this area because, in addition to pure pallet cargo loads, MPALPTS can accommodate rolling stock cargo (i.e. tanks, trucks, HMMMVs, etc.) while still maintaining aircraft feasibility with respect to aircraft center of balance, mandatory cargo separations, aircraft floor structural limitations, etc. Furthermore, while this research is currently restricted to C-5 and C-17 aircraft, MPALPTS is capable of modeling nearly any type of cargo aircraft and requires a limited number of assumptions thereby making it applicable to operational missions. To demonstrate its effectiveness, the load plans generated by MPALPTS are directly compared to those generated by the Automated Air Load Planning Software (AALPS) for a given cargo set; AALPS is the load planning software currently mandated for use in all Department of Defense load planning. While more time consuming than AALPS, MPALPTS required the same or fewer aircraft than AALPS in all test scenarios.