Dual-size nanofibers consisting of a random mixture of nano- and submicron-size nanofibers are promising structures for specific applications such as air filters because of their increased specific surface area and low pressure drop. Synthesis of dual-size nanofibers using one-step electrospinning was reported here for the first time. The formation of well-mixed nano- and submicron-size cellulose-polyvinylpyrrolidone nanofiber composites was accomplished utilizing the physical properties of TEMPO-oxidized cellulose nanofibers (i.e., high thixotropy and high magnitude of zeta potential) and tuning the charge of the polymer jet, which influences the formation and shape of Taylor cone, and Coulombic explosion. The dual-size nanofibers were then spun on the surface of a HEPA filter to obtain a multilayer air filter. Aerosol filtration measurements show that this multilayer air filter has an incredibly high performance, shown by the high quality factor (Qf), 0.117 Pa-1, which is 10 times the Qf of commercial HEPA filters.