Gardening and urban food production is an increasingly popular activity, which can improve physical and mental health and provide low cost nutritious food. However, the legacy of contamination from industrial and diffuse sources may have rendered surface soils in some urban gardens to have metals value in excess of recommended guidelines for agricultural production. The objective of this study was to establish the presence and spatial extent of soil metal contamination in Melbourne's residential and inner city community gardens. A secondary objective was to assess whether soil lead (Pb) concentrations in residential vegetable gardens were associated with the age of the home or the presence or absence of paint. The results indicate that most samples in residential and community gardens were generally below the Australian residential guidelines for all tested metals except Pb. Mean soil Pb concentrations exceeded the Australian HIL-A residential guideline of 300 mg/kg in 8% of 13 community garden beds and 21% of the 136 residential vegetable gardens assessed. Mean and median soil Pb concentrations for residential vegetable gardens was 204 mg/kg and 104 mg/kg (range <4–3341 mg/kg), respectively. Mean and median soil Pb concentration for community vegetable garden beds was 102 mg/kg and 38 mg/kg (range = 17–578 mg/kg), respectively. Soil Pb concentrations were higher in homes with painted exteriors (p = 0.004); generally increased with age of the home (p = 0.000); and were higher beneath the household dripline than in vegetable garden beds (p = 0.040). In certain circumstances, the data indicates that elevated soil Pb concentrations could present a potential health hazard in a portion of inner-city residential vegetable gardens in Melbourne.