Production of molecular scale palladium (Pd) nanoparticles (NPs) is important due to their catalytic function in electrochemical oxidation of a number of core fuel molecules in fuel cells. Biogenic methods offer an economic and environmentally friendly synthesis route. In this work, the electrochemically active bacterium Shewanella oneidensis MR-1 is employed as a reducing agent to generate PdNPs as well as a support for the immobilization of the PdNPs. The synthesis was carried out at 28 °C and pH 7.0, and completed within one hour. The PdNPs are monodisperse (6.2 nm) and located on the bacterial membrane surface. Mapping by conductive atomic force microscopy shows that the presence of these PdNPs promotes electron transfer and enhances the electric conductivity of the cells. Compared to electrodeposited PdNPs, PdNPs generated by S. oneidensis MR-1 catalyze electrochemically the oxidation of formate with 200 mV less over-potential. Notably they show unique selective activity toward electrochemical oxidation of formate, whereas no electrochemical catalysis was found for oxidation of ethanol, methanol and acetate. This work demonstrates a sustainable and low-cost method for producing efficient PdNP catalysts with high catalytic selectivity.