Highly active, durable and cost-effective electrocatalysts for water oxidation to evolve oxygen gas hold a key to a range of renewable energy solutions including water splitting and rechargeable metal-air batteries. Here, we report the synthesis of ultrathin nickel iron layered double hydroxide nanoplates on mildly oxidized multi-walled carbon nanotubes. Incorporation of Fe into the nickel hydroxide induced the formation of NiFe-layered double hydroxide. The nanoplates were covalently attached to a network of nanotubes, affording excellent electrical wiring to the nanoplates. The ultra-thin Ni-Fe layered double hydroxide nanoplates/carbon nanotube complex was found to exhibit unusually high electro-catalytic activity and stability for oxygen evolution and outperformed commercial precious metal Ir catalysts.