Considering the high demand for air quality, the development of biomass-based air filtration membranes with high air filtration efficiency and good stability is an urgent task. In this work, polyvinyl alcohol (PVA), gelatin (GA), and cellulose nanocrystals (CNC) were mixed and prepared into a membrane through an electrospinning method for air filtration. After a hydrophobic modification, the modified PVA/GA/CNC composite membrane showed excellent filtration efficiency for PM2.5 (97.65%) through the internal three-dimensional structure barrier and the electrostatic capture effect of the CNC with a negative charge, as well as a low-pressure drop (only 50 Pa). In addition, the modified PVA/GA/CNC composite membrane had good mechanical properties (maximum tensile fracture rate of 78.3%) and high stability (air filtration efficiency of above 90% after five wash-filter cycles and a high-temperature treatment at 200 °C). It is worth noting that the whole preparation process is completed without organic solvents, putting forward a new strategy for the construction of green air filtration membranes.