Moves to establish a botanical garden in St Kilda began as early as September 1859, and land granted for this purpose was gazetted on 1 August 1860. A competition for the design of the gardens was won by Tilman W. Gloystein, though the extent to which the design was implemented is not clear, the designs having been lost. In 1861 planting, trenching and fencing began, along with the gravelling of footpaths and walks. Nurseryman George Brunning was appointed first curator, and major planting began with plants mostly supplied from the Royal Botanic Gardens.
By the end of the 19th century the gardens boasted a gardener's lodge and associated buildings, seating, a summer house, connection to the reticulated water supply, entry gates, and a propagation and works area. In 1900 a fountain was added, followed by a lily pond in 1914. Other new structures included a vine-covered timber pergola, a steel archway, birdbath, aviary, drinking fountain, men's latrines and a pavilion in memory of Mr and Mrs Alfred Levi. The Alister Clark Memorial Rose Garden, developed on the north-east of the site by the St Kilda Council and the National Rose Society of Victoria to commemorate one of Australia's most notable horticulturists and rose-breeders, opened in 1950.