Regarded as both street art and vandalism, incidences of graffiti are recorded as early as 1859 when obscene words were added to notice boards in the Carlton Gardens. Public toilets were a favourite venue for such obscenities from the 1860s.
Political messages, especially socialist, were a prominent theme after World War II. The slogan 'Menzies must go' became so prevalent during the period 1952-56 that the Herald newspaper called for the 'scrawlers of this dirty work' to be prosecuted and the graffiti to be obliterated. A favourite site for such 'red slogans' was the walls of University High School on Royal Parade in Parkville. In preparation for the royal visit of 1954 this wall (dubbed the 'red slate') was demolished and the 'offensive Communist slogans' were removed from metropolitan railway buildings.
Graffiti addressed many of the major social and political issues that impacted on Melbourne life. One prominent message in 1955 read 'No troops for Malaya' while 'Ban H-tests' was daubed 3-feet high across the bases of the columns of the State Parliament House façade. Nor were more prosaic spaces spared. The message 'Out Bolte' appeared on the scoreboard of the Richmond Football Ground in 1958.
Politics was not the only theme for graffiti artists. The Herald newspaper (20 June 1930) recalled a Melbourne eccentric who travelled the suburbs 'adorning all the walls he could find with the one word, "Eternity"', predating Sydney's celebrated 'eternity man', Arthur Stace.
From 1979 BUGA-UP's (Billboard Utilising Graffitists Against Unhealthy Promotions) graffiti worked against sexist and tobacco advertising and marked graffiti's new power against large corporations. By contrast, the 'tagging' which appeared on trains was a territorial act which added nothing to public debates and instead aroused the public's ire. Attempts to incorporate graffiti into the mainstream by providing special 'graffiti walls' were always doomed to failure, as an ill-fated graffiti wall in the City Square proved. If graffiti had any power, it was in its ability to subvert.
While many of Melbourne's historic buildings inadvertently preserve historical graffiti in their fabric (such as in cells at the Old Melbourne Gaol), the 'Keon traitor to the ALP' graffiti was the first to be considered for classification by the National Trust as being of local heritage significance. Painted on a wall in Richmond in the 1950s, it referred to the role played by Stan Keon, then federal Australian Labor Party member and devout Catholic and anti-communist, in the split of the Democratic Labor Party from the ALP. Only weeks after its heritage value was publicised in 1999, the graffiti was itself graffitied.