The first waterside workers' unions in Australia were formed in Port Adelaide, Sydney, and Sandridge (Port Melbourne) in 1872. By 1889 there were notable waterfront unions in New South Wales, South Australia, Victoria and Western Australia. Although the various unions federated in March 1890 the Waterside Workers' Federation was not established until 7 February 1902 with Mr William Morris Hughes (Prime Minister of Australia, 1915-1923) elected its first President. The Waterside Workers' Federation was registered under the Commonwealth Conciliation and Arbitration Act on 1 July 1907 and the first comprehensive Commonwealth award for waterside workers dates from 13 December 1915. In January 1914 an office of the Waterside Workers’ Federation was established in Melbourne. After 1939 the Federation was located in Sydney. In order to manage the Waterside Workers' Federation Branches the Federal Executive, in 1902, established a Committee of Management (COM). The COM comprised delegates from the Executive of each Branch, and each Branch was entitled to one member for every 500 financial members. Furthermore, any of the COM’s resolutions that were approved by less than a 3/5 majority had to be submitted to at least 500 financial members of the rank and file for endorsement. Although designed to ease interstate rivalries this method of decision-making often exacerbated tension. The structure of the Waterside Workers' Federation remained largely unchanged until 1950 when it absorbed the Permanent and Casual Wharf Labourers' Union of Australia. In 1991 the Waterside Workers' Federation amalgamated with the Australian Foremen Stevedore Association but retained the name Waterside Workers' Federation of Australia. In 1993 the Waterside Workers' Federation of Australia joined with the Seamen's Union of Australia to form the Maritime Union of Australia.

The Newcastle Coal Trimmers' Friendly Accident Society was registered as a trade union in 1882 but went out of existence in the 1890s. The union was resuscitated and registered in 1901 as the Newcastle Coal Trimmers' Federal Union, after coal trimmers stopped work out of respect for the death of Queen Victoria and were penalised by employers. Coal trimmers were the waterside workers who loaded coal as cargo and into bunkers on steam ships. The union became the Newcastle Coal Trimmers Branch of the Waterside Workers' Federation in 1921.