Adding hydrocolloids to plant-based meat analogs is a useful way to modulate the extrudates texture. However, it can alter the rheological properties of the melt, hence affect the extrusion process and change the extrudate’s structure in an unknown manner. This study focuses on the influence of methyl cellulose (MC) as a model hydrocolloid on the mechanical properties of pea protein extrudates produced through high-moisture extrusion cooking. MC was introduced in solutions with different molecular weights at varying concentrations during extrusion. The study aims to assess whether MC affects the anisotropic structure of pea extrudates due to protein interactions or melt viscosity effects. Observations included changes in specific mechanical energy and die pressure, mechanical and rheological characterizations, and protein solubility analyses. MC decreased the melt viscosity during extrusion by 20% for all MC concentrations, although offline rheology measurements of protein-MC mixtures showed an increase dependent on concentration and type of MC. The meat analogs E-Moduli decreased due to MC addition by up to 75%. Protein analysis revealed protein-MC complexation, regardless of the MC molecular structure. These results show that anisotropic structuring cannot be predicted alone through offline rheological characterization. Understanding these protein-hydrocolloid interactions can improve plant-based products.