By using coarse-grained molecular dynamics simulations, we have investigated the structure and dynamics of supercooled single-chain cross-linked nanoparticle (SCNP) melts having a range of cross-linking degrees ϕ. We find a nearly linear increase in glass-transition temperature (Tg) with increasing ϕ. Correspondingly, we have also experimentally synthesized a series of polystyrene-based SCNPs and have found that the measured Tg estimated from differential scanning calorimetry is qualitatively consistent with the trend predicted by our simulation estimates. Experimentally, an increase in Tg as large as ΔTg = 61 K for ϕ = 0.36 is found compared with their linear chain counterparts, indicating that the changes in dynamics with cross-links are quite appreciable. We attribute the increase in Tg to the enlarged effective hard-core volume and the corresponding reduction in the free volume of the polymer segments. Topological constraints evidently frustrate the local packing. In addition, the introduction of intra-molecular cross-linking bonds slows down the structural relaxation and simultaneously enhances the local coupling motion on the length scales within SCNPs. Consequently, a more pronounced dynamical heterogeneity (DH) is observed for larger ϕ, as quantified by measuring the dynamical correlation length through the four-point susceptibility parameter, χ4. The increase in DH is directly related to the enhanced local cooperative motion derived from intra-molecular cross-linking bonds and structural heterogeneity derived from the cross-linking process. These results shed new light on the influence of intra-molecular topological constraints on the segmental dynamics of polymer melts.