Antimicrobial agents that have no or low cytotoxicity and high specificity are desirable to have no or minimal side effects. We report here the low cytotoxicity of polyvinyl alcohol-stabilized selenium (Se) nanoparticles and their differential effects on growth of S. aureus, a gram-positive bacterium and E. coli, a gram-negative bacterium. The nanoparticles were synthesised through redox reactions in an aqueous environment at room temperature and were characterised using UV visible spectrophotometry, transmission electron microscopy, dynamic light scattering and x-ray photoelectron spectroscopy. The nanoparticles showed low toxicity toward fibroblasts which remained more than 70% viable at Se concentrations as high as 128 ppm. The nanoparticles also exhibited very low haemolysis with only 18% of maximal lysis observed at a Se concentration of 128 ppm. Importantly, the nanoparticles showed strong growth inhibition toward S. aureus at a concentration as low as 1 ppm. Interestingly, growth of E. coli was unaffected at all concentrations tested. This study therefore strongly suggests that these nanoparticles should be investigated further to understand this differential effect as well as for potential advanced antimicrobial applications such as S. aureus infection-resisting, non-cytotoxic coatings for medical devices.