Pyrroloquinoline quinone (PQQ) is a 330 Da redox cofactor that is important for the metabolism of many microbes but is energetically costly to synthesize. Not all bacteria that produce enzymes that utilize PQQ are able to synthesize it. Instead, some organisms use the TonB-dependent transporter PqqU to scavenge trace quantities of PQQ from the environment. In this work we show that PqqU binds PQQ with very high affinity allowing it to scavenge useful quantities of PQQ from the environment at single digit nanomolar concentrations. To determine the structural basis for this high affinity we determined the cryo-electron microscopy structure of the 74 kDa Escherichia coli PqqU with bound PQQ at 1.99 Å. This high-resolution structure reveals PQQ coordination in exquisite detail, identifying 12 coordinating residues and 5 water molecules. It also reveals that PqqU undergoes significant conformational changes upon PQQ binding, with two extracellular loops enclosing the cofactor in an internal cavity. In concert with a plug domain that occludes the PqqU barrel, these loops allow the transporter to function via an airlock mechanism in which the PqqU channel is never simultaneously open to the extracellular space and periplasm, preventing harmful molecules from entering the cell. To determine residues critical for PqqU binding and import, we combined mutagenesis with transporter complementation assays, revealing key conserved arginine and tyrosine residues, which are critical for transporter function. We then used these key residues as a molecular signature to map the presence of PQQ scavenging via PqqU across Gram-negative bacteria. These metagenomic analyses revealed that PqqU is highly conserved across 22 Gram-negative bacterial phyla from diverse environments, including aquatic, terrestrial, host-associated, and extreme environments. This indicates that PQQ is ubiquitous, robust, and a vital nutrient. Importantly, we show that PQQ scavenging is a widespread strategy for obtaining this cofactor. Taken together, our results provide the molecular basis for PQQ scavenging by PqqU and highlight the cofactor’s broad environmental distribution and widespread use by Gram-negative bacteria.