The low availability of zinc (Zn) in soils and crops affects dietary Zn intake worldwide. This study sought to determine if the natural genetic variation in shoot Zn concentrations ([Zn](shoot)) is sufficient to pursue a crop improvement breeding strategy in a leafy vegetable crop. The gene-pool of Brassica oleracea L. was sampled using a large (n = 376) diversity foundation set (DFS), representing almost all species-wide common allelic variation, and 74 commercial varieties (mostly F(1)). The DFS genotypes were grown at low and high soil phosphorus (P) levels under glasshouse and field conditions, and also in a Zn-deficient soil, with or without Zn-fertilisation, in a glasshouse. Despite the large variation in [Zn](shoot) among genotypes, environment had a profound effect on [Zn](shoot) The heritability of [Zn](shoot) was significant, but relatively low, among 90 doubled-haploid (DH) lines from a mapping population. While several quantitative trait loci (QTL) associated with [Zn](shoot) occurred on chromosomes C2, C3, C5, C7, and C9, these were generally weak and conditional upon growth conditions. Breeding for [Zn](shoot) in B. oleracea is therefore likely to be challenging. Shoot P concentrations increased substantially in all genotypes under low soil Zn conditions. Conversely, only some genotypes had increased [Zn](shoot) at low soil P levels. Sufficient natural genetic variation may therefore exist to study some of the interactions between Zn and P nutrition.