The toxicity of nano-sized particles of mercury (NP–Hg), which are thought to be generated during the detoxification of methyl mercury (MeHg), may differ from that of MeHg, elemental Hg (Hg0), and inorganic Hg (I–Hg). From a human health perspective, it is important to evaluate the presence of NP-Hg in seafoods. We investigated the in vivo formation of NP-Hg in fish and shellfish, which are the main sources of Hg exposure in humans. NP-Hg was measured in 90 fish samples with single-particle inductively coupled plasma mass spectrometry (spICP-MS) after enzyme degradation with pancreatin and lipase. In addition to NP-Hg, total Hg (T-Hg), MeHg, and selenium (Se) concentrations were evaluated. Transient Hg signals were detected as nanoparticles from almost all samples by using spICP-MS. Higher particle number concentrations (CPN) were observed in the tuna–swordfish group than in the shellfish group (17.7 × 107 vs. 1.2 × 106 particles/g, respectively). Although the CPN and maximum particle mass increased significantly with increasing T-Hg concentration, the increase in CPN was greater than those in maximum particle mass. Assuming that the NP-Hg detected was HgSe (tiemannite) and spherical based on previous reports, the maximum particle diameter was estimated to be 89 nm. The mean dietary exposures to NP-Hg, T-Hg, and MeHg were estimated to be 0.067, 5.75, and 5.32 μg/person per day, respectively. Generation of NP-Hg was inferred to be widespread in marine animals, with a preferential increase in the number of particles rather than an increase in particle size. The mean dietary exposure to NP-Hg in Japanese people was estimated to be 1.2 ng/kg body weight (BW) per day. Compared to PTWI of 4 μg/kg BW per week (0.57 μg/kg BW per day) derived by JECFA (2011), the health risk from redissolved I–Hg from NP-Hg is small.