While genome size limits the minimum sizes and maximum numbers of cells that can be packed into a given leaf volume, mature cell sizes can be substantially larger than their meristematic precursors and vary in response to abiotic conditions. Mangroves are iconic examples of how abiotic conditions can influence the evolution of plant phenotypes. Here, we examined the coordination between genome size, leaf cell sizes, cell packing densities and leaf size in 13 mangrove species across four sites in China. Four of these species occurred at more than one site, allowing us to test the effect of climate on leaf anatomy. We found that genome sizes of mangroves were very small compared to other angiosperms, but, like other angiosperms, mangrove cells were always larger than the minimum size defined by genome size. Increasing mean annual temperature of a growth site led to higher packing densities of veins (Dv) and stomata (Ds) and smaller epidermal cells but had no effect on stomatal size. In contrast to other angiosperms, mangroves exhibited (1) a negative relationship between guard cell size and genome size; (2) epidermal cells that were smaller than stomata; and (3) coordination between Dv and Ds that was not mediated by epidermal cell size. Furthermore, mangrove epidermal cell sizes and packing densities covaried with leaf size. While mangroves exhibited coordination between veins and stomata and attained a maximum theoretical stomatal conductance similar to that of other angiosperms, the tissue-level tradeoffs underlying these similar relationships across species and environments were markedly different, perhaps indicative of the unique structural and physiological adaptations of mangroves to their stressful environments.