Selenite is extremely biotoxic, and as a result of this, exploitation of microorganisms able to reduce selenite to non-toxic elemental selenium (Se⁰) has attracted great interest. In this study, a bacterial strain exhibiting extreme tolerance to selenite (up to 100 mM) was isolated from the gut of adult Monochamus alternatus and identified as Proteus mirabilis YC801. This strain demonstrated efficient transformation of selenite into red selenium nanoparticles (SeNPs) by reducing nearly 100% of 1.0 and 5.0 mM selenite within 42 and 48 h, respectively. Electron microscopy and energy dispersive X-ray analysis demonstrated that the SeNPs were spherical and primarily localized extracellularly, with an average hydrodynamic diameter of 178.3 ± 11.5 nm. In vitro selenite reduction activity assays and real-time PCR indicated that thioredoxin reductase and similar proteins present in the cytoplasm were likely to be involved in selenite reduction, and that NADPH or NADH served as electron donors. Finally, Fourier-transform infrared spectral analysis confirmed the presence of protein and lipid residues on the surfaces of SeNPs. This is the first report on the capability of P. mirabilis to reduce selenite to SeNPs. P. mirabilis YC801 might provide an eco-friendly approach to bioremediate selenium-contaminated soil/water, as well as a bacterial catalyst for the biogenesis of SeNPs.