Air Trans Africa was formed by Jack Malloch in 1964 after his first company, Rhodesian Air Services failed in 1962. It operated a Super Constellation, a Douglas C-54 and a DH114 Heron aircraft. The airline's financial crises were compounded when the government of Southern Rhodesia, under Ian Smith, unilaterally declared independence on November 11, 1965.

It was a charter airline flying cargo and/or passengers to many different destinations throughout Europe and Africa. The company (in chronological order):

• Carried mercenaries to the Congo in 1964 to help the government of Moise Tshombe quell the insurgency of a group of Congolese rebels called the Simba.
• Acted as a charter carrier to the Biafran Civil War in Nigeria. During the civil war the C-54 was impounded and the crew imprisoned for a time in 1967.
• Operated a Lockheed Super Constellation (VP-WAW) under the name of Afro Continental Airways after UDI for a weekly service from Salisbury to Windhoek.
• Obtained a fleet of Douglas DC-7C and DC-7CF aircraft (with the assistance of the Rhodesian Government) which were registered in Gabon, when the airline became a major part of the Rhodesian sanctions-busting operations. They flew beef to Gabon, from where it was flown out by aircraft of its associate company Affretair. Essential materials for the Rhodesian security forces were brought into the country on the return flights. Affretair migrated to Zimbabwe after independence, when it replaced Air Trans Africa.