Monodispersed Pd nanoparticles (8, 11, and 13 nm in iameter) as confirmed by high resolution transmission electron microscopy were prepared via the reverse microemulsion method and deposited on structured supports consisting of carbon nanofibers (CNF) grown on sintered metal fibers (SMF). The CNF/SMF supports were subjected to oxidative treatments to introduce O-functional groups on the CNF surface. These groups were characterized by temperature-programmed decomposition (TPD) and X-ray photoelectron spectroscopy. The catalysts were used to study (a) the effect of Pd size and (b) the effect of the support nature on the selective acetylene hydrogenation. Antipathetic size dependence of TOF disappeared at particle size bigger than 11 nm. Initial selectivity to ethylene was found size-independent. The deactivation due to coke deposition was faster for smaller particles. The structure-sensitivity relations for the catalysts investigated are discussed in terms of “geometric” and “electronic nature” of the size effect and rationalized regarding Pd-Cx phase formation which is size-dependent. Supports with increased acidity diminished the formation of coke and changed the byproduct distribution toward ethane.