In this study, we combined two wheat proteins, gliadin (Gli)/glutenin (GT), and modified potato starch (MPS) into composites using extrusion. In the Gli/GT-MPS composites, we studied the structural dynamics of proteins and starch, protein-starch interactions, protein properties, and composite morphology in relation to mechanical and barrier properties. Materials with different ratios of Gli/GT and MPS were extruded using either glycerol or glycerol-water at 110 and 130 °C. For the first time, a hierarchical hexagonal structure of Gli proteins was observed in Gli-MPS composite at both extrusion temperatures. The higher temperature (130 °C) induced a higher degree of protein cross-links, an increase in the polymer size, and formation of β-sheets compared to 110 °C. The combination of plasticizers (glycerol and water) favored a micro-structural morphology with improved gelatinization of starch, processability, as well as strength, stiffness, and extensibility of GT-MPS composites. The highest amount of the oxidized proteins was observed in the samples with the highest protein content and at high extrusion temperature. The Gli- and GT-MPS (30/70) samples showed promising oxygen barrier properties under ambient testing conditions. These findings provide in-depth information for tailoring the structural-functional relationship of the Gli/GT-potato starch composites for their promising use in designing various green materials.