The Connellan Airways route structure from a 1957 advertising card. The airline was based at Alice Springs and scheduled services followed an 'out and back' pattern, with each circuit taking up to three days to complete. The service was in fact more akin to a local bus service, albeit extending over an enormous area, than a traditional airline service.

Most of the stops were made at Stations and the primary purpose of the service was the transport of mail, freight and 'local' passenger traffic. The subsidy provided by the government, through DCA, was established on the basis of most Stations receiving one mail delivery per fortnight, although some Stations received more visits depending on traffic. Special lower rates were established for certain perishable items of freight such as fresh vegetables, eggs and butter.

Because of the generally small aircraft used, special flights directly to a particular destination would often be operated in preference to tying up the regular service with passenger traffic. Stops could be made on request at some Stations that were normally overflown.

A typical fortnightly service, taken from the 1 January 1957 timetable, served the country to the north-east of Alice Springs and went as follows:-

Sunday: Alice Springs; Alcoota*; Utopia; Murray Downs; Kurindi*; Hatches Creek; Elkedra; Annitowa; Mt Isa.

Monday: Mt Isa; Camooweal*; Alexandria; Alroy; Brunette Downs; Cresswell Downs; Mallapunyah; McArthur River; Borroloola; Wollogorang; Calvert Hills.

Tuesday: Calvert Hills; Cresswell Downs; Anthony Lagoon; Eva Downs; Rockhampton Downs; Tennant Creek; Kurindi; Hatches Creek; Alice Springs.

* = stop on request only, schedule and daylight permitting, at extra charge

Fares covered light refreshments. Meals and accomodation, if necessary, were charged directly by the Station concerned, although many Stations made no charge at all.

By the mid-1960s Connellan Airways was serving 132 places on regular scheduled services, using De Havilland Herons and Beechcraft Twin Bonanzas.

Renamed Connair in 1970, the airline played a major part in the evacuation of Darwin in the aftermath of cyclone Tracy in 1974. Tragedy struck in 1977 when a disgruntled former pilot crashed a stolen aircraft into the airline's office at Alice Springs, killing Eddie's son Roger, two engineers and a female clerk. Eddie struggled on for another two years, but on 21 December 1979 he sold the airline he had made into a byword throughout the outback of central Australia to East-West Airlines for $1.8 million.