Tasman Cargo Airlines commenced operations as Premier Airlines on 5 September 1994, headquartered in Melbourne, Victoria and flying a Boeing 727-100 freighter on behalf of DHL. Due to International Civil Aviation Organization "Stage III" aircraft noise restrictions this aircraft was withdrawn from service the following year and a Boeing 727-200 was acquired. In late 1996 Premier Airlines changed its name to Asian Express Airlines to better reflect its role in flying for DHL in the Asian region, and moved its headquarters to Auckland Airport. The airline's domicile in New Zealand was short-lived; it was established at its current location by early 1998.