An efficient, durable and low cost air-cathode is essential for a high performance metal-air battery for practical applications. Herein, we report a composite bifunctional catalyst, Co3O4 nanoparticles-decorated carbon nanofibers (CNFs), working as an efficient air-cathode in high performance rechargeable Zn-air batteries (ZnABs). The particles-on-fibers nanohybrid materials were derived from electrospun metal-ion containing polymer fibers followed by thermal carbonization and a post annealing process in air at a moderate temperature. Electrochemical studies suggest that the nanohybrid material effectively catalyzes oxygen reduction reaction via an ideal 4-electron transfer process and outperforms Pt/C in catalyzing oxygen evolution reactions. Accordingly, the prototype ZnABs exhibit a low discharge-charge voltage gap (e.g. 0.7 V, discharge-charge at 2 mA cm(-2)) with higher stability and longer cycle life compared to their counterparts constructed using Pt/C in air-cathode. Importantly, the hybrid nanofiber mat readily serves as an integrated air-cathode without the need of any further modification. Benefitting from its efficient catalytic activities and structural advantages, particularly the 3D architecture of highly conductive CNFs and the high loading density of strongly attached Co3O4 NPs on their surfaces, the resultant ZnABs show significantly improved performance with respect to the rate capability, cycling stability and current density, promising good potential in practical applications.