Solid-state proton nuclear magnetic resonance (NMR) has been used to investigate the structure and dynamics of a thermoplastic polyurethane elastomer (TPE) filled with carbon nanofibers (CNF's) for shape-memory applications. The TPE soft segments are above their glass transition temperature (T-g) at ambient temperature and give rise to relatively narrow (similar to 2 kHz) signals in the solid-state proton spectrum. The introduction of CNF's leads to a concentration-dependent shifting and broadening of the signals, while the proton spin-lattice and spin-spin relaxation times are not significantly altered, showing that the broadening is inhomogeneous and related to the difference in magnetic susceptibility between the TPE and the CNF's. Proton spin diffusion experiments reveal the onset of stress-induced crystallinity as the samples are stretched to 60%, and stretching to 1000% leads to crystallization at the CNF surface and increased separation between the CNF's and the mobile amorphous phase of the TPE. The implications for the mixing of polymers and CNF's are considered.