It was first unofficially located on the corner of Alfred and King Street, currently the site of the ambulance station next to the Gympie Hospital. Following approximately 50 burials at this site, the Tozer Park Road Cemetery was opened on 1 December 1869. The first burial register was started at that time.
The flood-prone town of Gympie was subjected to diseases such as diphtheria, and the Tozer Park Cemetery bore the blame. It was found that the ground was too low and hard digging, resulting in shallow burials that caused distressing odours. Tozer Park Cemetery was closed in 1886.
The cemetery was relocated to its current location on Corella Road at Two Mile, and an area of 60 acres was granted. Families were granted new plots in lieu of plots already purchased in the old cemetery. They were also able to exhume loved ones and move their headstones to place in the Two Mile Cemetery and family graves were established. However many headstones remained until the 1980s.
The first person to discover gold in the Gympie area, James Nash is buried in the cemetery. In 1911, a memorial to the leader of the Irish revolutionary movement, John Flood, was established in recognition of his work towards Irish nationality.
Gympie Family History Society
The Gympie Family History Society moved the remaining headstones to the new cemetery with the help of the Queensland Heritage Council. These headstones are grouped together in the pioneer section. The Gympie Family History Society coordinates regular cemetery walks with up to 60 people attending. These walks are known as Cemetery Crawls.  Participants learn more about the pioneering families that created the town.
- Environmental Protection Agency (Queensland) (2000). Heritage Trails of the Great South East. State of Queensland. p. 154. ISBN 0-7345-1008-X.
- A History of Gympie Cemeteries by Neil Priddy, Historical Section Gympie Library BRN:62788
- Gympie Burial Register Index, ISBN 0 646 249 258
- "Cemeteries". Gympie Regional Council. Retrieved 25 May 2012.
-  CWGC Cemetery Report.
- "Secrets from the grave". The Gympie Times. 2 March 2012. Retrieved 25 May 2012.
- "Cemetery Crawls". Gympie Family History Society Inc. Retrieved 19 March 2016.