Microcapsules with high mechanical stability and elasticity are desirable in a variety of contexts. We report a single-step method to fabricate such microcapsules by microfluidic interfacial complexation between high stiffness cellulose nanofibrils (CNF) and an oil-soluble cationic random copolymer. Single-capsule compression measurements reveal an elastic modulus of 53 MPa for the CNF-based capsule shell with complete recovery of deformation from strains as large as 19%. We demonstrate the ability to manipulate the shell modulus by the use of polyacrylic acid (PAA) as a binder material, and observe a direct relationship between the shell modulus and the PAA concentration, with moduli as large as 0.5 GPa attained. These results demonstrate that CNF incorporation provides a facile route for producing strong yet flexible microcapsule shells.