Starch is added to meat analogues for binding and water holding. In this study, we investigate whether starch can have an additional role as a structuring agent. Therefore, different types of starch were combined with wheat gluten at various amounts and sheared in a High Temperature Shear Cell to determine how starch influences the structuring behavior of gluten–starch blends. The starches were chosen based on their diverse amylose contents, leading to different technological properties. Remarkable differences were found between the starches investigated. The addition of Amioca starch (containing 1% amylose) had a strong negative influence on the ability of gluten to form fibers. Maize starch (25% amylose) and Hylon VII (68% amylose) formed fibrous materials up to high starch additions. The pre-gelatinizing of maize starch further increased the ability of gluten–starch mixtures to form fibrous structures. The influence of the different types of starch on the hardness, deformability, and stiffness of the sheared samples was also assessed, revealing a spectrum of achievable properties through the addition of starch. Most remarkable was the formation of a material with anisotropy in Young’s modules. This anisotropy is also found in chicken meat, but not in protein-based fibrous materials. Furthermore, it was observed that the pre-gelatinization of starch facilitated fiber formation. A similar effect of pre-gelatinizing the starch was found when using faba bean meal with added wheat gluten, where fibrous structures could even be formed in a recipe that previously failed to produce such structures without pre-treatment.