Palladium nano-network structures supported on electrospun carbon nanofibers (Pd-NNSs-ECNFs) were successfully prepared through a novel K2PdIICl4/K4FeII(CN)6 cyanogel method. The Pd-NNSs have features and properties of small particle size, low dimensionality, quantum effect and high stability. SEM, TEM and XPS were used to characterize the Pd-NNSs-ECNFs. The Pd-NNSs-ECNFs were used as a catalyst in different types of Suzuki coupling reactions to evaluate the catalytic abilities. Results showed that the heterogeneous catalyst (Pd-NNSs-ECNFs) had high catalytic activity (high yields to the products) to the Suzuki coupling reactions in an environmentally friendly solvent system (Ethanol/H2O). The catalyst can be recycled by the filtration, and reused seven times without losing the catalytic activity. This research opened new applications of Pd-NNSs-ECNFs in the area of green chemistry.