Bacteria have developed fine-tuned responses to cope with potential zinc limitation. The Zur protein is a key player in coordinating this response in most species. Comparative proteomics conducted on the cyanobacterium Anabaena highlighted the more abundant proteins in a zur mutant compared to the wild type. Experimental evidence showed that the exoprotein ZepA mediates zinc uptake. Genomic context of the zepA gene and protein structure prediction provided additional insights on the regulation and putative function of ZepA homologs. Phylogenetic analysis suggests that ZepA represents a primordial system for zinc acquisition that has been conserved for billions of years in a handful of species from distant bacterial lineages. Furthermore, these results show that Zur may have been one of the first regulators of the FUR family to evolve, consistent with the scarcity of zinc in the ecosystems of the Archean eon.