Advancement of electrocatalysts relies on the construction of both a highly efficient catalytic center and a highly conductive network support. Herein, we prepared a 3D interwoven structure with Pd atoms deposited on homogeneously bound MnO2 nanowires and carbon nanotubes (CNTs) (Pd/MnO2-CNT), allowing the combination of superior catalytic performance of atomic Pd incorporated in the metal oxide and the high conductivity of CNT. Using this nanocomposite, stable bifunctional oxygen reduction/evolution reaction (ORR/OER) was achieved. Pd/MnO2-CNT displayed a large Pd mass activity for ORR, which is two magnitudes higher than that of Pd/CNT and 5-fold higher than that of the state-of-the-art Pd-based electrocatalysts operated in alkaline medium. Application of this composite catalyst in Zn-air batteries generates significantly high efficiency and cycling stability. Experimental and theoretical studies revealed that MnO2 provided stronger electronic metal-support interaction than CNT. Pd single atoms doped in MnO2 work synergistically with the surrounding metal sites to activate molecular oxygen, and display optimized binding strength to reaction intermediates. Our strategy can be generalized to design new single atom electrocatalysts for numerous functionalities.