The point was originally a small tidal island, Bennelong Island, that largely consisted of rocks with a small beach on the western side. The island was located on the tip of the eastern arm of Sydney Cove and was apparently separated from the mainland at high tide. For a brief period in 1788, this relatively isolated protrusion into Port Jackson (Sydney's natural harbour) was called Cattle Point as it was used to confine the few cattle and horses that had been brought from Cape Town by Governor Phillip with the First Fleet.
The area at that time was also strewn with discarded oyster shells from thousands of years of gathering by the local aboriginal women. Those shells were regathered by the newly arrived convict women and burnt to make lime for cement mortar. The point was called Limeburners' Point for that reason, though those shells only furnished enough lime to make a single building, the two-storey government house.
In the early 1790s, the Aborigine Bennelong—kidnapped and employed as a cultural interlocutor by the British—persuaded New South Wales Governor Arthur Phillip to build a brick hut for him on the point, giving it its name.
In December 1798, a half-moon battery was constructed at the extreme northern end of the Point, mounted with guns from HMS Supply.
In the period from 1818 to 1821, the tidal area between Bennelong Island and the mainland was filled with rocks excavated from the Bennelong Point peninsula. The entire area was leveled to create a low platform and to provide suitable stone for the construction of Fort Macquarie. While the fort was being built, a large portion of the rocky escarpment at Bennelong Point was also cut away to allow a road to be built around the point from Sydney Cove to Farm Cove. This was known as Tarpeian Way.
The existence of the original tidal island and its rubble fill were largely forgotten until the late 1950s when both were rediscovered during the excavations related to the construction of the Sydney Opera House. Prior to the Opera House's construction, Bennelong Point had housed Fort Macquarie Tram Depot.