C4 photosynthesis has evolved multiple times in the angiosperms and typically involves alterations to the biochemistry, cell biology and development of leaves. One common modification found in C4 plants compared with the ancestral C3 state is an increase in vein density such that the leaf contains a larger proportion of bundle sheath cells. Recent findings indicate that there may be significant intraspecific variation in traits such as vein density in C4 plants but to use such natural variation for trait-mapping, rapid phenotyping would be required. Here we report a high-throughput method to quantify vein density that leverages the bundle sheath-specific accumulation of starch found in C4 species. Starch staining allowed high-contrast images to be acquired permitting image analysis with MATLAB- and Python-based programmes. The method works for dicotyledons and monocotolydons. We applied this method to Gynandropsis gynandra where significant variation in vein density was detected between natural accessions, and Zea mays where no variation was apparent in the genotypically diverse lines assessed. We anticipate this approach will be useful to map genes controlling vein density in C4 species demonstrating natural variation for this trait.