Here, we investigated the structure of natural montmorillonite (MMT) and modified Cloisite C15A (MMT pre-intercalated with a dimethyl-dehydrogenated tallow quaternary ammonium surfactant) nanoclays in the wheat gluten-urea matrix in order to obtain a nanocomposite with improved barrier and mechanical properties. Small-angle X-ray scattering indicated that the characteristic hexagonal closed packed structure of the wheat gluten-urea matrix was not found in the CISA system and existed only in the 3 and 5 wt % MMT composites. SAXS/WAXS, TGA, and water vapor/oxygen barrier properties indicated that the dispersion of the C15A clay was somewhat better than the natural MMT clay. Confocal laser scanning microscopy showed MMT clay clusters and C15A clay particles dispersed in the protein matrix, and these were preferentially oriented in the extrusion direction only at 5 wt % of the CIS clay. The water vapor/oxygen barrier properties were improved with the presence of clay. Independent of the clay content used, the stiffness decreased and the extensibility increased in the presence of C15A due to the surfactant induced changes on the protein. The opposite "more expected" clay effect (increasing stiffness and decreasing extensibility) was observed for the MMT composites.