In this work, a novel reinforcing filler, millet gliadin (MG), was used for the improvement of the mechanical properties of zein nanofibers. The structural and physicochemical properties of MG were compared with those of zein, and the influence of MG on the morphology, physical properties, and molecular structure of zein nanofibers was investigated. The results indicated that MG has an obviously smaller weight-average molecular weight (7623) in comparison to zein (13,330). Transmission electron microscopy showed that zein molecules more easily form aggregates with larger diameters than MG molecules in acetic acid. At a concentration of 30% (w/v), MG exhibited a significantly higher viscosity (0.66 ± 0.03 Pa·s) than zein (0.32 ± 0.01 Pa·s), indicating the stronger interactions of MG molecules. With the incorporation of MG, the tensile strength was significantly increased to 49.32 MPa (ZM-1/2), which is 2.08 times and 4.45 times higher than that of pure zein nanofibers (ZM-1/0) and MG nanofibers (ZM-0/1-1), respectively. Moreover, zein/MG composite nanofibers exhibited improved water stability. Fourier transform infrared spectra showed evidence of the hydrogen bonding interaction between zein and MG. Therefore, MG is a good candidate for use as a natural reinforcing filler in electrospun nanofibers made of biopolymers.