Electrically conductive polypyrrole-polyvinylpyrrolidone (PPy-PVP) nanofiber mats with a core-shell structure have been successfully fabricated by a two-step process: the formation of FeCl3-containing PVP nanofiber mat by electrospinning, and the vapor-phase polymerization (VPP) of pyrrole monomer on the mat in a sealed chamber at room temperature. Surface morphology and chemical composition of the PPy-PVP mat were characterized by SEM, EDX and FTIR analyses. The as-prepared nonwoven mat was composed of PPy-PVP nanofibers with an average diameter of 300 nm. The sheet conductivity of the nanofiber mat was measured to be approximately 0.01 S/cm by a four-point probe. We have also investigated gas-sensing properties of PPy-PVP nanofiber mat upon exposure to methanol vapor. The PPy-PVP nanofiber sensors were observed to have excellent methanol-sensing performance. The nanofiber-based core-shell nanostructure could give an opportunity to fabricate a highly sensitive and fast response sensor due to its high surfaceto-volume ratio.