The Constuction Forestry Mining and Energy Union is the result of a series of amalgamations during the early 1990s. Prior to amalgamation there were numerous unions spread across construction, forestry, mining and energy industries. Those unions amalgamated along industry lines to form each of the divisions of the CFMEU. Each division operates autonomously, with its own membership, executive, resources, industry policies and campaigns. These divisions date as far back as the mid-nineteenth century and include such notable unions as the Australasian Coal and Shale Employees' Federation (the Miners' Federation), the Building Workers' Industrial Union of Australia, the Australian Timber Workers' Union, the Federated Furnishing Trade Society of Australasia, the Operative Plasterers' Federation of Australia, the Operative Painters' and Decorators' Union of Australia, and the Federated Engine Drivers' and Firemen's Association of Australasia.

The Federated House and Ship Painters, Paperhangers and Decorators Employees' Association of Australasia became the Operative Painters and Decorators of Australasia in 1915. In 1918 it changed its name to the Operative Painters' and Decorators' Union of Australia. Seventy-five years later, the union amalgamated to form the Construction Forestry Mining and Energy Union in 1993.

The Building Workers' Industrial Union of Australia formed from the Amalgamated Society of Carpenters and Joiners of Australia in 1945 but was deregistered in 1948. An anti-communist faction of the union established a new Amalgamated Society of Carpenters and Joiners in 1950 which eventually became part of the Australian Workers' Union. The Building Workers' Industrial Union formally reconstituted in 1962. Members of the Federated Bricklayers' Association of Australia (deregistered 1950) and the Slaters Tilers Shinglers and Roof Fixers Union of Australia (deregistered 1976) also joined. In 1991 the BWIU amalgamated with the timber unions to become the Australian Timber and Allied Industries Union and Building Workers' Industrial Union (ATAIU & BWIU) Amalgamated Union and to eventually be part of the Construction Forestry Mining and Energy Union in 1993.

The Federated Engine Drivers' and Firemen's Association of Australasia dates back to local engine drivers' unions on Australian goldfields but was not registered federally until 1908. Predecessors include the Newcastle Colliery Engine Drivers' Union (1889-1921), the Newcastle Crane Employees' Union (1893-1915), the Shore Engine Drivers' and Firemen's Union of New South Wales (1901-1908), the Steam Crane Engine Drivers' Society of New South Wales (1901-1910), the New England Engine Drivers' Association (amalgamated in 1908), the Amalgamated Engine Drivers' Association of Tasmania and the United Certificated Engine Drivers' Association of Victoria. It was deregistered in 1949 but formed again in 1950 under the same name. It was amalgamated with the Construction Forestry and Mining Employees' Union and the Operative Plasterers' and Plaster Workers' Federation of Australia in 1992 to form the Construction Forestry Mining and Energy Union. The union represented engine drivers and firemen, crane drivers, dynamo and boiler attendants, forklift drivers and plant operators in hospitals, abattoirs, dockyards, brickworks, mines, power stations and factories.