To improve the ability to recycle polyethylene (PE)-coated paperboard, one solution may be to use nanofibrillated cellulose (NFC) to generate a layer that should weaken when wet that leads to a clean separation between the polymer film and the pulp fibers. This NFC layer has the potential to improve the package’s oxygen and grease barrier properties, but this system has not been explored in the literature. In this study, papers coated with zero, 2, and 4 g/m2 of NFC were laminated with a PE film under a range of pressing temperatures and times at a constant pressing pressure. A model was developed to predict fiber recovery given the air permeability of the paper, pressing time, polymer temperature, and paper void volume. The recyclability or fiber recovery was evaluated in addition to the adhesive strength. Samples with the NFC layer had much improved fiber recovery because the NFC layer gives a good separation during the recycling operation. The model predictions were compared to the experiments.