Selenium-reducing microorganisms produce elemental selenium nanoparticles with particular physicochemical properties due to an associated organic fraction. This study identified high-affinity proteins associated with such bionanominerals and with nonbiogenic elemental selenium. Proteins with an anticipated functional role in selenium reduction, such as a metalloid reductase, were found to be associated with nanoparticles formed by one selenium respirer, Sulfurospirillum barnesii.