Three-dimensional structures of functionally uncharacterized proteins may furnish insight into their functions. The potential benefits of three-dimensional structural information regarding such proteins are particularly obvious when the corresponding genes are conserved during evolution, implying an important function, and no functional classification can be inferred from their sequences. The Bacillus subtilis Maf protein is representative of a family of proteins that has homologs in many of the completely sequenced genomes from archaea, prokaryotes, and eukaryotes, but whose function is unknown. As an aid in exploring function, we determined the crystal structure of this protein at a resolution of 1.85 A. The structure, in combination with multiple sequence alignment, reveals a putative active site. Phosphate ions present at this site and structural similarities between a portion of Maf and the anticodon-binding domains of several tRNA synthetases suggest that Maf may be a nucleic acid-binding protein. The crystal structure of a Maf-nucleoside triphosphate complex provides support for this hypothesis and hints at di- or oligonucleotides with either 5'- or 3'-terminal phosphate groups as ligands or substrates of Maf. A further clue comes from the observation that the structure of the Maf monomer bears similarity to that of the recently reported Methanococcus jannaschii Mj0226 protein. Just as for Maf, the structure of this predicted NTPase was determined as part of a structural genomics pilot project. The structural relation between Maf and Mj0226 was not apparent from sequence analysis approaches. These results emphasize the potential of structural genomics to reveal new unexpected connections between protein families previously considered unrelated.