Vegetable gardens in cities provide communities with fresh vegetables but also may contribute towards public exposure to metals present in soil from historical pollution. Contamination of some Melbourne garden soils with Pb (range 12.9-773 mg kg-1 in soil) was found with some soils exceeding the Australian human health screening criteria for residential land use of 300 mg kg-1. Cadmium concentrations (0.12-1.04 mg kg-1) were above the ambient background soil concentrations of <1 mg kg-1. Nickel concentrations (7.6-40.5 mg kg-1) and Cr (11.6-49.4 mg kg-1) were within the range of expected ambient background concentrations. Distance from the nearest arterial road, house age and the likely use of lead-based paints were the main factors explaining approximately 75% of soil Pb variability in garden soils. Metal concentrations in garden soils of wooden houses were found to be significantly higher than the garden soil of brick and concrete houses (Pb (p < 0.0001)) and Cd (p < 0.001)). Significant correlations were found between backyard garden soil metal concentration and house age for Pb (R2 = 0.83, p < 0.0001) and Cd (R2 = 0.40, p < 0.0002) and the distance from arterial roads for Pb (R2 = 0.38, p < 0.002), while Cr and Ni are related to soil characteristics cation exchange capacity, organic matter, and pH. Vegetable garden with elevated Pb and Cd had recognizable risk factors such as older, painted structures on adjacent houses and closer proximity to arterial roads with higher frequency traffic.