Bacteria and archaea import molybdenum and tungsten from the environment in the form of the oxyanions molybdate (MoO42-) and tungstate (WO42-). These substrates are captured by an external, high-affinity binding protein, and delivered to ATP binding cassette transporters, which move them across the cell membrane. We have recently reported a crystal structure of the molybdate/tungstate binding protein ModA/WtpA from Archaeoglobus fulgidus, which revealed an octahedrally coordinated central metal atom. By contrast, the previously determined structures of three bacterial homologs showed tetracoordinate molybdenum and tungsten atoms in their binding pockets. Until then, coordination numbers above four had only been found for molybdenum/tungsten in metalloenzymes where these metal atoms are part of the catalytic cofactors and coordinated by mostly non-oxygen ligands. We now report a high-resolution structure of A. fulgidus ModA/WtpA, as well as crystal structures of four additional homologs, all bound to tungstate. These crystal structures match X-ray absorption spectroscopy measurements from soluble, tungstate-bound protein, and reveal the details of the distorted octahedral coordination. Our results demonstrate that the distorted octahedral geometry is not an exclusive feature of the A. fulgidus protein, and suggest distinct binding modes of the binding proteins from archaea and bacteria.