Simultaneous removal of selenite and tellurite from synthetic wastewater was achieved through microbial reduction in a lab-scale upflow anaerobic sludge blanket reactor operated with 12 h hydraulic retention time at 30 °C and pH 7 for 120 days. Lactate was supplied as electron donor at an organic loading rate of 528 or 880 mg COD L day. The reactor was initially fed with a synthetic influent containing 0.05 mM selenite and tellurite each (phase I, day 1-60) and subsequently with 0.1 mM selenite and tellurite each (phase II, day 61-120). At the end of phase I, selenite and tellurite removal efficiencies were 93 and 96%, respectively. The removal percentage dropped to 87 and 81% for selenite and tellurite, respectively, at the beginning of phase II because of the increased influent concentrations. The removal efficiencies of both selenite and tellurite were gradually restored within 20 days and stabilized at ≥ 97% towards the end of the experiment. Powder X-ray diffraction and Raman spectroscopy confirmed the formation of biogenic Se(0), Te(0), and Se(0)-Te(0) nanostructures. Scanning transmission electron microscopy coupled with energy-dispersive X-ray spectroscopy showed aggregates comprising of Se(0), Te(0), and Se-Te nanostructures embedded in a layer of extracellular polymeric substances (EPS). Infrared spectroscopy confirmed the presence of chemical signatures of the EPS which capped the nanoparticle aggregates that had been formed and immobilized in the granular sludge. This study suggests a model for technologies for remediation of effluents containing Se and Te oxyanions coupled with biorecovery of bimetal(loid) nanostructures.