Plasticized cassava starch matrix composites reinforced by a multi-wall carbon nanotube (MWCNT)-hercynite (FeAl<inf>2</inf>O<inf>4</inf>) nanomaterial were developed. The hybrid nanomaterial consists of FeAl<inf>2</inf>O<inf>4</inf> nanoparticles anchored strongly to the surface of the MWCNT. This nano-hybrid filler shows an irregular geometry, which provides a strong mechanical interlocking with the matrix, and excellent stability in water, ensuring a good dispersion in the starch matrix. The composite containing 0.04 wt.% of the nano-hybrid filler displays increments of 370% in the Young's modulus, 138% in tensile strength and 350% in tensile toughness and a 70% decrease in water vapor permeability relative to the matrix material. All of these significant improvements are explained in terms of the nano-hybrid filler homogenous dispersion and its high affinity with both plasticizers, glycerol and water, which induces crystallization without deterioration of the tensile toughness.