A new approach to immobilizing zero-valent iron nanoparticles (ZVI NPs) into electrospun polymer nanofibers with enhanced mechanical properties for environmental applications is presented. In this approach, multiwalled carbon nanotubes (MWCNTs) are mixed with polyacrylic acid (PAA)/polyvinyl alcohol (PVA) mixture polymer solution for subsequent electrospinning to form uniform nanofibers. The MWCNT-incorporated PAA/PVA nanofibers are crosslinked and then used as a nanoreactor to complex Fe(III) ions through binding with the PAA carboxyl groups for the reductive formation of ZVI NPs. The MWCNT-incorporated PAA/PVA nanofibers before and after immobilization with ZVI NPs are characterized using scanning electron microscopy, energy dispersive spectroscopy, transmission electron microscopy, Fourier transform infrared spectroscopy, thermogravimetric analysis, and mechanical property measurements. We show that the mechanical properties of uniform nanofibrous mats with and without ZVI NPs are significantly enhanced even with only 1.0 wt% MWCNTs incorporated. The MWCNT-reinforced PAA/PVA nanofibrous mats containing ZVI NPs (1.6 nm) display excellent capability to decolorize model dyes such as methyl blue, acridine orange, and acid fuchsine with a decoloration percentage of more than 90%. Likewise, the same nanofibrous mats are found to be able to effectively degrade trichloroethylene, a model chlorinated hydrocarbon contaminant, with a degradation efficiency approaching 93%. The MWCNT-reinforced PAA/PVA nanofibrous mats may be used for generating other functionalized nanofiber-based complex materials with enhanced mechanical properties for applications in environmental remediation, catalysis, sensing, and biomedical sciences.