This study analyzed the effect of the inclusion of legume-derived proteins, specifically pea and fava bean protein, with varying solubility levels on the expansion of corn starch. Three different proteins exhibiting low, medium, or high solubility were mixed with corn starch to obtain blends containing 15%, 25%, and 35% (w/w) of the protein. Extrusion was performed on a twin-screw extruder at three different screw speeds (200, 400, and 600 rpm), a moisture content of 16% (w.b.), and a die temperature of 140°C. Obtained extrudates were analyzed for their expansion, unit density, and hydration properties, namely, water solubility index (WSI) and water absorption index (WAI). Extrudates containing the protein with the highest solubility showed different patterns than those that had proteins with low or medium solubility. Expansion ratio (ER) increased from a maximum of 3.55 ± 0.24 for pure corn starch up to 5.45 ± 0.43 when incorporating 35% of the protein with medium solubility but significantly decreased down to 1.24 ± 0.08 when incorporating 35% of the most soluble protein. The influence on the system parameters, as well as on the hydration properties, was also greatest for the blends containing the protein with the highest solubility. Even though significant Pearson correlations were observed between protein solubility and ER (r = −0.579), unity density (r = 0.614), WSI (r = −0.634), torque (r = −0.612), as well as specific mechanical energy (r = −0.451), further research is needed to evaluate if the solubility is indeed the reason for certain behaviors or if other protein characteristics are more critical for expansion.