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 Maritime Union of Australia was formed in 1993 with the merging of several maritime unions, principally the Waterside Workers’ Federation of Australia and the Seamen’s Union of Australia. For a brief time Joint General Secretaries controlled the Union and the representation and responsibilities of the former Waterside Workers’ Federation and the Seamen’s Union were differentiated. Following the waterfront dispute of 1997-1998, however, the Maritime Union of Australia became consolidated as a single entity.