Federation Square is located on the traditional lands of the Kulin Nation. The site of Federation Square at early colonial settlement was an open swampy area of public land reserved between Flinders Street, the Yarra River, and the extension of Swanston Street to the main river crossing point. Government buildings were supplanted by the first rail line and station from 1859, a use which gradually expanded through the nineteenth century until the whole area was railway lines and railyards, with Princes Bridge Station serving lines to the north east on Flinders Street. Batman Avenue, which curved along parallel to the river up to Swanston Street, was developed in 1890 along with the construction of the final Princes Bridge.

A number of proposals for roofing the rail yards were made through the twentieth century, first in the 1920s, then revived in the 1950s and 60s as part of wider efforts to develop public buildings, purpose-built public institutions, and public plazas to remedy the paucity of public open space within the city grid. Ultimately only the few railway lines adjacent to Flinders Street were built over, with a pair of sixteen storey office blocks named Princes Gate Plaza (also known as the Gas and Fuel Buildings) with Princes Bridge Station below, and a raised plaza on the corner of Swanston Street, completed in 1967.

A much longed for civic square for Melbourne was instead developed on the corner of Swanston and Collins from 1966. A new design replaced the initial square in 1980. Built to a competition-winning permanent design by Denton Corker Marshall, Melbourne City Square opened in May 1980. By 2000, DCM’s Melbourne City Square was replaced with a much simpler square design. This was in turn demolished in 2017 for the Melbourne Metro tunnel construction.

In 1994 the Victorian State Government, led by Premier Jeff Kennett, announced that the Gas and Fuel Buildings would be replaced by a development celebrating the Centenary of Federation on 1 January 2001.  In 1996 demolition of the Gas & Fuel buildings began and an international design competition was held to develop a ‘unique 21^st century civic and cultural facility’ that was to include a plaza, a Cinemedia centre, a performance space, a small gallery, a wintergarden and shops and cafes. From 177 entries a short list of 5 were chosen, and on 28^th July 1997, the winner was announced: London-based Lab Architecture Studio, led by Australian Peter Davidson and US-born Donald Bates, in association with the Melbourne architects Bates Smart.

When the winning design was announced, the first of what would become many changes to the original brief was also made; that the proposed ‘civic and cultural facility’ should also house the Australian art collection of the National Gallery of Victoria in an enlarged gallery on the site.  The final design was announced in July 1998. It was substantially different in detail but retained the general layout of the winning scheme, and employed the same architectural language of ‘cranked’ angular geometries, scattered vertical ‘shards’, and folded abstract patterned facades. Construction began a month later with the challenge of decking the railway lines.

In 1997 a Civic and Cultural Charter was developed and agreed to by the State Government of Victoria and City of Melbourne to guide the future operations of the Square, balancing the civic and public uses and the commercial tenancies. It was assumed that the commercial activities would underpin the operational costs of managing the Square as a whole. In 1999 the Victorian Government established Fed Square Pty Ltd to operate the Square on its behalf as the sole shareholder, and to oversee construction.

The design of Federation Square provided impetus for public interest in the project and its design and debate. The western ‘shard’, a free standing four storey element proposed for the corner of Flinders and Swanston Street, was particularly controversial. A key concern, raised soon after the winner was announced, was that this element of the design would block views to St Pauls Cathedral from Princes Bridge. Following an inquiry, then Premier Steve Bracks announced on 17 February 2000 that the western ‘shard’ would be reduced in height to no more than 8m. The decision drew protests from the architectural community.

Construction was fast-tracked in the hopes of completing by early 2001, which meant detailed design occurred just before construction and problems resolved through ‘on the spot’ decisions. The tight timelines and the complexity of bringing to fruition the design of ‘cranked’ angles in three dimensions, a process that required sophisticated computer modelling, meant the final cost was four times the original budget. Finally, nearly two years after the centenary of Federation, the Premier of Victoria, the Hon. Steve Bracks officially opened Federation Square to the public on Saturday 26 October 2002. The Ian Potter Centre: NGV Australia and ACMI were fully completed later that year, and other tenancies opened over the next 12 months. The Square and its various occupants were immediately popular, drawing millions of visitors in the first year.

The larger amphitheatre-like space of the Square has since become the focus for numerous major public events. The first was New Year’s Eve 2002, followed in January 2003 by crowds gathering to watch the Australian Open on the screen. In September 2003 the AFL Grand Final was streamed live, as were the 2006 Melbourne Commonwealth Games. It has been used as a site of protest, from an Iraq war demonstration in 2002, a Work Choices rally in 2005, and on 13 February 2008 people gathered to watch Prime Minister Kevin Rudd issue the formal apology to the Stolen Generations. It has been used for numerous events, from Indigenous ceremonies, to festivals, markets, fashion shows, public lectures, films and concerts. The Ian Potter Centre: NGV Australia has hosted Australian art shows, from the permanent collection to curated shows, and ACMI has become a focus for screen culture, with film festivals, special events, accessing the State Film collection, and drawing thousands to the many screen and movie culture based shows in the basement Screen Gallery. The Melbourne Visitors Centre in the basement accessed via the truncated corner shard is a starting point for many visitors and tourists into the site.

There have been few alterations to the buildings and spaces since construction. In 2009, the entry to ACMI was reconfigured to allow entry only from the Square rather than also from Flinders Street, a permanent, interactive exhibition Screen Worlds: The Story of Film, Television and Digital Culture was installed, and the Mediateque was developed, where the public can access much of the film and video collection. Since September 2015 the upper floors of the Yarra building have been home to the Koorie Heritage Trust. A weather protection canopy designed by Melbourne-based architect Peter Maddison, of Maddison Architects, was added to the eastern extremity of the main Square in 2014.