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 Fremantle Lumpers' Union was the first known union of unskilled labour in Western Australia. It was formed after a recruiting mission to the west by the Adelaide Lumpers' Union in 1889 and was inspired, perhaps, by the solidarity shown in the Great Dock Strike workers in Britain of that year. It joined the Waterside Workers' Federation in 1910 but broke away in 1933 after a dispute with the Federal Executive of the Waterside Workers' Federation over the method of collection of union dues. It reaffiliated in 1946.