The Eastern and Australian Mail Steam Company altered the dynamics of sea transport between China and Australia in the late nineteenth century. From 1873 to 1880, this shipping company initiated a new, regular, and permanent route between China and Australia that assisted in the development of stronger trade relationships. The company fulfilled this on the back of a mail contract with the Queensland government. What transpired during the mail contract, its impacts, and its legacies have left an indelible, though unrecognised, positive mark on Australia's trade relationships with China. As such, Eastern and Australian were one of the pioneers in brokering regular international trade routes for colonial Australian merchants and governments. They also became an integral element in the eventual transition from sail to steam, not only along the China-Australia route but also for all Australian international shipping.