Rice grain is known to accumulate methylmercury (MeHg) and has been confirmed to be the major pathway of MeHg exposure to residents in mercury (Hg) mining areas in China. Selenium (Se) supplementation has been proven to be effective in mitigating the toxicity of Hg. To understand how Se supplementation influences soil Hg speciation, a wide range of Se (0–500 mg/kg) was applied to Hg polluted paddy soils in this study, which decreased MeHg concentration in soil from 2.95 ± 0.36 to 0.69 ± 0.16 μg/kg (or 77%). After Se addition, humic acid state Hg (F4) was transformed into strong-complexed state Hg (F5), indicating that Hg bound up to the non-sulfur functional groups of humic acid (non-RSH) was released and reabsorbed by strong binding Se functional group (F5). As a result, inorganic Hg (IHg) was reduced by >48%, 18%, and 80% in root, stem, and grain, respectively, however, the reduction was not apparent in leaf. Substantial reductions were also found for MeHg in grain and root, but not in stem and leaf. Soil is suggested to be the main source of both MeHg and IHg in rice grain. Such a finding may provide an idea for improving Hg-polluted paddies through controlling soil IHg and MeHg. Further research on the molecular structure of the strong-complexed Hg in F5 should be conducted to elucidate the mechanism of Hg-Se antagonism.