Background: Selenium (Se) is an essential trace element in most organisms but has to be carefully handled since there is a thin line between beneficial and toxic concentrations. Many bacteria have the ability to reduce selenite (Se(IV)) and (or) selenate (Se(VI)) to red elemental selenium that is less toxic. Results: A strictly aerobic bacterium, Comamonas testosteroni S44, previously isolated from metal(loid)-contaminated soil in southern China, reduced Se(IV) to red selenium nanoparticles (SeNPs) with sizes ranging from 100 to 200 nm. Both energy dispersive X-ray Spectroscopy (EDX or EDS) and EDS Elemental Mapping showed no element Se and SeNPs were produced inside cells whereas Se(IV) was reduced to red-colored selenium in the cytoplasmic fraction in presence of NADPH. Tungstate inhibited Se(VI) but not Se(IV) reduction, indicating the Se(IV)-reducing determinant does not contain molybdenum as co-factor. Strain S44 was resistant to multiple heavy and transition metal(loid)s such as Se(IV), As(III), Cu(II), and Cd(II) with minimal inhibitory concentrations (MIC) of 100 mM, 20 mM, 4 mM, and 0.5 mM, respectively. Disruption of iscR encoding a transcriptional regulator negatively impacted cellular growth and subsequent resistance to multiple heavy metal(loid)s. Conclusions: C. testosteroni S44 could be very useful for bioremediation in heavy metal(loid) polluted soils due to the ability to both reduce toxic Se(VI) and Se(IV) to non-toxic Se (0) under aerobic conditions and to tolerate multiple heavy and transition metals. IscR appears to be an activator to regulate genes involved in resistance to heavy or transition metal(loid)s but not for genes responsible for Se(IV) reduction.