Introduction: One-third of the human population consumes insufficient zinc (Zn) to sustain a healthy life. Zn deficiency can be relieved by increasing the Zn concentration ([Zn]) in staple food crops through biofortification breeding. Rice is a poor source of Zn, and in countries predominantly relying on rice without sufficient dietary diversification, such as Madagascar, Zn biofortification is a priority. Methods: Multi-environmental trials were performed in Madagascar over two years, 2019 and 2020, to screen a total of 28 genotypes including local and imported germplasm. The trials were conducted in the highlands of Ankazomiriotra, Anjiro, and Behenji and in Morovoay, a location representative of the coastal ecosystem. Contributions of genotype (G), environment (E), and G by E interactions (GEIs) were investigated. Result: The grain [Zn] of local Malagasy rice varieties was similar to the internationally established grain [Zn] baseline of 18–20 μg/g for brown rice. While several imported breeding lines reached 50% of our breeding target set at +12 μg/g, only few met farmers’ appreciation criteria. Levels of grain [Zn] were stable across E. The G effects accounted for a main fraction of the variation, 76% to 83% of the variation for year 1 and year 2 trials, respectively, while GEI effects were comparatively small, contributing 23% to 9%. This contrasted with dominant E and GEI effects for grain yield. Our results indicate that local varieties tested contained insufficient Zn to alleviate Zn malnutrition, and developing new Zn-biofortified varieties should therefore be a priority. GGE analysis did not distinguish mega-environments for grain [Zn], whereas at least three mega-environments existed for grain yield, differentiated by the presence of limiting environmental conditions and responsiveness to improved soil fertility. Discussion: Our main conclusion reveals that grain [Zn] seems to be under strong genetic control in the agro-climatic conditions of Madagascar. We could identify several interesting genotypes as potential donors for the breeding program, among those BF156, with a relatively stable grain [Zn] (AMMI stability value (ASV) = 0.89) reaching our target (>26 μg/g). While selection for grain yield, general adaptation, and farmers’ appreciation would have to rely on multi-environment testing, selection for grain [Zn] could be centralized in earlier generations.