A supramolecular polymer blend, formed via π-π interactions between a π-electron rich pyrenyl end-capped oligomer and a chain-folding oligomer containing pairs of π-electron poor naphthalene-diimide (NDI) units, has been reinforced with cellulose nanocrystals (CNCs) to afford a healable nanocomposite material. Nanocomposites with varying weight percentage of CNCs (from 1.25 to 20.0 wt %) within the healable supramolecular polymeric matrix have been prepared via solvent casting followed by compression molding, and their mechanical properties and healing behavior have been evaluated. It is found that homogeneously dispersed films can be formed with CNCs at less than 10 wt %. Above 10 wt % CNC heterogeneous nanocomposites were obtained. All the nanocomposites formed could be rehealed upon exposure to elevated temperatures although, for the homogeneous films, it was found that the healing rate was reduced with increasing CNC content. The best combination of healing efficiency and mechanical properties was obtained with the 7.5 wt % CNC nanocomposite which exhibited a tensile modulus enhanced by as much as a factor of 20 over the matrix material alone and could be fully rehealed at 85 °C within 30 min. Thus it is demonstrated that supramolecular nanocomposites can afford greatly enhanced mechanical properties relative to the unreinforced polymer, while still allowing efficient thermal healing.