In the present study, we were able to produce composites of wheat gluten (WG) protein and a novel genetically modified potato starch (MPS) with attractive mechanical and gas barrier properties using extrusion. Characterization of the MPS revealed an altered chain length distribution of the amylopectin fraction and slightly increased amylose content compared to wild type potato starch. WG and MPS of different ratios plasticized with either glycerol or glycerol and water were extruded at 110 and 130 °C. The nanomorphology of the composites showed the MPS having semicrystalline structure of a characteristic lamellar arrangement with an approximately 100 Å period observed by small-angle X-ray scattering and a B-type crystal structure observed by wide-angle X-ray scattering analysis. WG has a structure resembling the hexagonal macromolecular arrangement as reported previously in WG films. A larger amount of β-sheets was observed in the samples 70/30 and 30/70 WG-MPS processed at 130 °C with 45% glycerol. Highly polymerized WG protein was found in the samples processed at 130 °C versus 110 °C. Also, greater amounts of WG protein in the blend resulted in greater extensibility (110 °C) and a decrease in both E-modulus and maximum stress at 110 and 130 °C, respectively. Under ambient conditions the WG-MPS composite (70/30) with 45% glycerol showed excellent gas barrier properties to be further explored in multilayer film packaging applications.