In May 1829 Captain Charles Fremantle raised a flag on the south head of the Swan River taking formal possession in the name of His Majesty King George IV of all that part of New Holland, that the continent of Australia was called until the 1850s, which was not included within the territory of New South Wales.^[6] In 1843 work started on a channel through the rock bar at the mouth of the Swan River; this was followed by the construction of a river jetty at the end of Cliff Street, known as the North Jetty. In 1866 the construction of the first bridge across the Swan River created the eastern boundary of the harbour.^[7]

In 1881 the railway line between Fremantle and Guildford was completed. It terminated in Fremantle at the river end of Cliff Street. Despite a number of proposals and recommendations there was only limited facilities to unload vessel in Fremantle. Many vessels were wrecked due to winter storms, so the Fremantle Chamber of Commerce campaigned for the establishment of a safe harbour in Fremantle.

In 1890 Western Australia was granted responsible government. Premier John Forrest was committed to establishing Western Australia's main harbour at Fremantle despite opposition from postal authorities in other colonies who preferred Albany. In 1891 C. Y. O'Connor, an Irish born civil engineer who had extensive experience in New Zealand, arrived in Western Australia and was appointed Engineer-in-Chief for Western Australia. In 1892 O'Connor presented two plans for building Fremantle Harbour.^[7]

Initial construction started in 1892, focused on the north mole and blasting the rock bar across the river mouth. Because of its proximity to Fremantle blasting was slow. Construction of the south mole commenced in August 1894 using rock from Arthur Head and Rocky Bay. It was not until late 1896 that dredging of the blasted rock harbour began; spoil from the dredging work was used to fill the embankment for Victoria Quay. With the gold rush putting pressure on Fremantle harbour, a temporary wharf 91 metres (299 ft) in length was added to the south mole as well as a temporary 304-metre (997 ft) wharf on the north mole.

Victoria Quay was substantially finished in 1897, and effectively opened when SS Sultan berthed there on 4 May 1897.^[7][8]

The sheds on the quay were named alphabetically, and modified over time. In 1995 E Shed was moved from alongside the wharf to land near the Cliff Street entrance. Today, the building houses the E Shed Markets.

During the 1950s, Customs and Police offices^[9] were located on the border of the quay and the railway marshalling yard.^[10] The structure on Victoria Quay now called the Old Police Station was known between 1906 and 1966 as the Immigration Buildings.^[11]

Fremantle Ports have 14 "harbourcams" located or focused upon Victoria Quay, with the images being broadcast via their web page.^[12]

32°03′00″S 115°44′46″E / 32.050°S 115.746°E / -32.050; 115.746