Herein, catalytically active cyclodextrin (CD) nanofibers loaded with in situ formed Pd nanoparticles (Pd-NPs) were prepared by solution electrospinning. Cyclodextrin (CD) acted as a reducing agent and catalyzed the formation of noble metal nanoparticles, e.g., palladium (Pd) over the reduction from Pd²⁺ to metallic Pd⁰, without requiring any other reducing agent. Nanofibers were produced by the electrospinning of CD molecules from aqueous and DMF solutions containing two different Pd loadings (1 and 2 wt% with respect to CD). The electrospinning of these solutions could give rise to bead-free CD nanofibers whose diameters showed variations depending on the solvent-type and the Pd content used: the nanofibers electrospun from DMF solutions were smaller in diameter than those produced from aqueous solutions. Furthermore, increasing Pd loading decreased the nanofiber diameter. TEM, HRTEM, STEM and SAED analyses confirmed the presence of homogeneously distributed polycrystalline Pd-NPs in the size range of 3–5 nm throughout the nanofiber matrix. XPS experiments demonstrated the presence of a higher proportion of metallic Pd⁰ atoms owing to the efficient reduction of Pd²⁺ by CD molecules. Lastly, the catalytic activity of the nanocomposite nanofibers was explored by the reduction of a nitroarene compound, p-nitrophenol (PNP), to p-aminophenol (PAP), and high catalytic activity of the nanofibers was observed.