Pollution by metalloids, e.g., tellurite and selenite, is of serious environmental concern and, therefore, there is an increasing interest in searching for ecologically friendly solutions for their elimination. Some microorganisms are able to reduce toxic tellurite/selenite into less toxic elemental tellurium (Te) and selenium (Se). Here, we describe the use of the environmentally relevant β-proteobacterium Aromatoleum sp. CIB as a platform for tellurite elimination. Aromatoleum sp. CIB was shown to tolerate 0.2 and 0.5 mM tellurite at aerobic and anaerobic conditions, respectively. Furthermore, the CIB strain was able to reduce tellurite into elemental Te producing rod-shaped Te nanoparticles (TeNPs) of around 200 nm length. A search in the genome of Aromatoleum sp. CIB revealed the presence of a gene, AzCIB_0135, which encodes a new methyltransferase that methylates tellurite and also selenite. AzCIB_0135 orthologs are widely distributed in bacterial genomes. The overexpression of the AzCIB_0135 gene both in Escherichia coli and Aromatoleum sp. CIB speeds up tellurite and selenite removal, and it enhances the production of rod-shaped TeNPs and spherical Se nanoparticles (SeNPs), respectively. Thus, the overexpression of a methylase becomes a new genetic strategy to optimize bacterial catalysts for tellurite/selenite bioremediation and for the programmed biosynthesis of metallic nanoparticles of biotechnological interest.