The airline was established and started operations in 1949. It began in Tamworth as a one-aircraft, one-pilot operation, known as Tamworth Air Taxi Service (soon after to be shortened to Tamair), serving farming communities in New South Wales and Queensland. After 36 years of expansion and amalgamation with several smaller commuter operators, the current name was adopted in 1987. Australian Airlines purchased 26% of Eastern Australian Airlines from East-West Airlines in 1988, and the airline became a wholly owned subsidiary in 1991. Qantas purchased Australian Airlines in 1992.
In 2002, Qantas merged its Mildura-based subsidiary Southern Australia Airlines with Eastern, the resulting operation using the Eastern name.
In August 2008 it was announced that Eastern Australia would shortly commence operating 72-seat Bombardier Dash 8 Q400 aircraft on services to regional centres in New South Wales, supplementing services with smaller 50-seat Dash 8s and allowing the removal of 36-seat Dash 8s from service on some routes altogether with the retirement of all 100 series Dash 8s.
An Eastern Australia Airlines Bombardier DHC-8 Q200 at rest at the Sydney main base. The pink ribbon forward of the entry door is to advertise QantasLink's support of breast cancer research, while aft of the door is the Oneworld logo
Eastern Australia Airlines operates services to the following domestic scheduled destinations: