The effect of polysaccharide coatings on the stability and release characteristics of selenium nanoparticles (SeNPs) was evaluated by comparing the characteristics of chitosan-coated SeNPs (CS-SeNPs) and sodium carboxymethyl cellulose-coated SeNPs (CMC-SeNPs). The release characteristics of SeNPs were investigated in storage conditions, gastrointestinal conditions, and free radical systems. CMC-SeNPs formed dimers or trimers, whereas CS-SeNPs were monodispersed but formed large aggregates in a pH range of 7.4–8.25. Upon 50 days of storage at 30 ◦C, both CMC-SeNPs and CS-SeNPs were converted to Se4+. SeNPs exhibited a lower release rate in simulated gastrointestinal conditions than in free radical systems. SeNPs release in ABTS and superoxide anion free radical systems followed the first-order and Korsmeyer-Peppas models, respectively, indicating that SeNP release is mainly governed by dissolution mechanisms. Additional studies are needed to examine the potential environmental effects and biological activity of the Se4+ released from SeNPs.