Originally raised in 1912 as a Militia formation, the brigade was later re-raised in 1916 as part of the First Australian Imperial Force during World War I.

During World War II the brigade undertook defensive duties and training in Victoria and Queensland, before being deployed to New Guinea in 1943.

At this time, the brigade's constituent units were located around Shepparton, Wangaratta, Seymour, Moonee Ponds, Ascot Vale, Coburg, Carlton and Newmarket.

Under the command of Brigadier General Harold Elliott, the brigade was formed as part of the expansion of the AIF that was undertaken in 1916 following the conclusion of the Gallipoli campaign.

[9] For the next two and a half years the brigade saw service in the trenches along the Western Front in France and Flanders, taking part in actions at Bullecourt, Polygon Wood, Villers–Bretonneux and along the St Quentin Canal.

[10] Their final engagement came around Beaurevoir in late September and into early October 1918 when the Australians undertook operations to penetrate the German defences along the Hindenburg Line.

[11] Severely depleted and suffering from manpower shortages that was the result of the combined effect of a decrease in the number of volunteers arriving from Australia and the decision to grant home leave to men who had served for over four years,[12] the Australian Corps was subsequently withdrawn from the line for rest on 5 October, upon a request from the Australian prime minister, Billy Hughes.

[19] Nevertheless, the following year the Army's budget was halved in response to the resolution of the Washington Naval Treaty which theoretically removed the threat to Australia posed by Japan,[19] and as the scope of the compulsory training scheme was scaled back, the authorised strength of each battalion was reduced to just 409 men of all ranks, maintaining a skeleton organisation of just three companies.

[25] From 1936 onwards attempts were made to improve the conditions of service and to reinvigorate the training program, while individual units began to undertake their own recruiting campaigns,[26] however it was not until 1938, as tensions grew in Europe, that an attempt was made to expand the establishment of the Militia and a concerted effort to evaluate the readiness of individual units was undertaken at the annual camp that year.

The 15th Brigade received considerable criticism following its camp, with the inspecting officer giving a negative review to all three infantry battalions, although the 58th was singled out for the harshest assessment.

[30] Throughout 1941 the 15th Brigade, consisting of the 57th/60th, 58th and 59th Infantry Battalions, was stationed around Seymour, where it was mobilised for full time service following Japan's entry into the war.

Assigned a role in the feint against Salamaua,[35] the brigade's most significant actions came in June and into July when they were involved in the fighting around Bobdubi Ridge.

In early 1944, the brigade was formed up for battle in its entirety and was attached to the 7th Division for its campaign in the Markham and Ramu valleys, arriving at Dumpu on 7 January to begin their advance.

[40] By that time it had grown to a full brigade-group, consisting of a headquarters, three infantry battalions—the 24th, 57th/60th and 58th/59th Battalions—and supporting elements including a signals section, a flamethrower platoon, three troops of tanks from the 2/4th Armoured Regiment, a section of engineers from the 15th Field Company, a company from the 1st New Guinea Infantry Battalion, the 266th Light Aid Detachment, as well as military police, postal and dental units and a detachment from the Australian New Guinea Administrative Unit.