The park is located on the shore of the bay in Sydney Harbour from which the suburb is named.

It was originally called Warringa Park, but was renamed in 1926 in honor of William Anderson who was the Mayor of the local municipality of North Sydney from 1914 to 1918.

On 17 July 1934, thousands gathered in Anderson Park to watch as Charles Kingsford Smith and Captain Patrick Gordon Taylor took off from there in their single-engined Lockheed Altair for a promotional flight over Sydney.

[2] Originally, they had planned to take off from the middle of Macquarie Street in Sydney, but when the local council denied permission, they transported their aeroplane by barge to Neutral Bay.

The Altair had recently been shipped from America on the deck games court of the SS Mariposa, and had the word "ANZAC" painted on the side, though this had to be covered with brown paper due to Australian law prohibiting the use of this word for commercial purposes.