Nonwoven membranes based on electrospun fibers are of great interest in applications such as biomedical, filtering, and protective clothing. The poor mechanical performance is a limitation, as is some of the electrospinning solvents. To address these problems, porous nonwoven membranes based on nanofibrillated cellulose (NFC) modified by a hydroxyethyl cellulose (HEC) polymer coating are prepared. NFC/HEC aqueous suspensions are subjected to simple vacuum filtration in a paper-making fashion, followed by supercritical CO(2) drying. These nonwoven nanocomposite membranes are truly nanostructured and exhibit a nanoporous network structure with high specific surface area, as analyzed by nitrogen adsorption and FE-SEM. Mechanical properties evaluated by tensile tests show high strength combined with remarkably high strain to failure of up to 55%. XRD analysis revealed significant fibril realignment during tensile stretching. After postdrawing of the random mats, the modulus and strength are strongly increased. The present preparation route uses components from renewable resources, is environmentally friendly, and results in permeable membranes of exceptional mechanical performance.