The development of plant-based foods has emerged as a promising strategy to decrease meat consumption. Using predominantly globular plant proteins challenges the crafting of cohesive, viscoelastic, and anisotropic structures similar to animal meat. In this study, we investigated the effect of incorporating low concentrations (<1%, w/w) of the polar gelatin or the non-polar zein on the mechanical properties of high moisture meat analogue prototypes. These proteins were studied in both particulate (bulk) and nano-fibrillated forms. Building on our previous work, soy protein (68% protein) and mung bean protein (81% protein) concentrates were chosen based on their distinct protein purity and high propensity to rearrange into new ordered secondary structural elements upon extrusion. Gelatin and zein were incorporated into the extrusion process via aqueous dispersion in particulate form or previously converted into nanofibers (210–440 nm diameter) using food-grade electrospinning. The incorporation of both fillers (either particulate or fibrillate) decreased the elasticity and Warner-Bratzler Shear Force (WBSF, known to be inversely correlated to meat tenderness) of mung bean extrudates. However, the addition of 0.1% fibrillated gelatin or particulate/fibrillated zein increased up to 44% or 22% the WBSF of soy extrudates, respectively. In all cases, the incorporation of fillers caused dramatic concentration-dependent changes in the secondary structures (FTIR) of soy proteins and the water mobility (LF-NMR) of extrudates. This work highlights the potential of multifunctional fillers and the combination of top-down (extrusion) and bottom-up (fibrillation) approaches to reduce the tenderness gap between animal meat and structured foods made with less-refined plant-protein fractions.