The objective of this work is to formulate a zein-based nanocomposite for the delivery of natural polyphenols. A proprietary atomizing/antisolvent precipitation (AAP) process was used to prepare carboxymethyl chitosan (CMC)-coated zein/soy lecithin (SL) nanoparticles (ZLC NPs). At a suitable mass ratio of zein/SL/CMC (100 : 30 : 30), ZLC NPs with desirable redispersibility and physicochemical stability were successfully fabricated. After that, resveratrol (Res) as the representative natural polyphenol was encapsulated in ZLC NPs. The optimized Res/ZLC NPs exhibited a spherical morphology, small size (259.43 ± 2.47 nm), large zeta potential (-47.7 ± 0.66 mV), and high encapsulation efficiency (91.32 ± 4.01%) and loading capacity (5.27 ± 0.35%). Further characterization indicated that Res was encapsulated in the hydrophobic core of the ZLC matrix in an amorphous state. Compared to free Res, Res/ZLC NPs showed a 2.55-fold increase in the Res dissolution rate, a 2.27-fold increase in bioaccessibility, and a 1.69-fold increase in ABTS˙+ scavenging activity. Also, Res/ZLC NPs showed a higher Res retention rate (>68.0%) than free Res (<35.0%) over 45 days of storage. Therefore, ZLC NPs have promising potential as vehicles for natural polyphenols.