The role of cross-linking in dictating the microstructural and mechanical properties in ethylene-propylene-diene-monomer rubber (EPDM) and EPDM/ULDPE blends cross-linked by different sulfur amounts is investigated by solid-state 1H time-domain NMR spectroscopy and tensile-tests. Analyses of spin-spin relaxation time (T2), by combining free-induction decay (FID), magic-sandwich echo-FID, and Hahn-echo experiments demonstrate a reduction in crystal-amorphous interface regions of pure ultralow-density polyethylene (ULDPE) upon curative addition. The blends demonstrate a complete loss of these fractions due to curative-induced plasticization and solvation by polyethylene segments of EPDM. Cross-link densities, quantified by the magnitude of residual dipolar coupling constant (Dres), arising from topological restrictions to segmental motions, are measured by multiple-quantum experiments. The entanglement-dominated EPDMs demonstrate a significant reduction in ultimate tensile properties with increasing Dres. The analogous blends yield similar Dres values up to 0.36 phr of free sulfur. Thereafter, a deviation from the cross-linking trend of the EPDMs is observed with the blends approaching a cross-linking limit, thus emphasizing the migration of additives to the amorphous phase of the ULDPE. From the additional contributions of solvation and complex entanglement scenarios in the blends, restoration and even significant enhancement in ultimate tensile strength are achieved. Limitations in applying the popular Mooney–Rivlin analysis are also briefly discussed.