The development of the Gardens site began in 1858, two years after the municipality of Ballarat was formed. A Committee of Management was established and a decision was made to convert the Ballarat Police Horse Paddock into a botanical garden. At the same time it was decided to construct a road on the west side of Yuille's Swamp (Lake Wendouree) to be known as Wendouree Parade.

A design competition for the garden was won by Messrs Wright and Anderson. The founding Curator, George Longley who had trained in horticulture at Lowther Castle in England, worked long and hard at converting the design into a reality until his death in 1898. For the first 2 years he lived in a tent in the vicinity of The Robert Clark Centre and directed contractors to clear trees and cart soil from Yuille's Swamp.

The second Curator's Cottage built in 1877

In association with Baron von Mueller, plants and seeds were received from the Melbourne and Geelong Botanical Gardens and Longley set about a substantial propagation program in a nursery ground that he had laid out in 1859. In the 1860s the principal tree plantings that still give The Gardens their unique character were established. Of particular importance is the South Avenue of Giant Redwoods which was planted in 1863.

In the 1870s there was a fascination with exotic species from around the world and avid 'plant hunting' resulted in a collection of great diversity. It was at this time that the Ballarat Fish Acclimatisation Society was founded and the first zoo, with deer and aviaries, was established. Construction works included a timber Camelia House and nursery buildings.