Electrical control of magnetism has the potential to bring about revolutionary new spintronic devices(1-5), many of which rely on efficient manipulation of magnetic domain walls in ferromagnetic nanowires(2-4). Recently, it has been shown that voltageinduced charge accumulation at a metal-oxide interface can influence domain wall motion in ultrathin metallic ferromagnets(6- 8), but the effects have been relatively modest and limited to the slow, thermally activated regime(9). Here we show that a voltage can generate non-volatile switching of magnetic properties at the nanoscale by modulating interfacial chemistry rather than charge density. Using a solid-state ionic conductor as a gate dielectric(10,11), we generate unprecedentedly strong voltage-controlled domain wall traps that function as non-volatile, electrically programmable and switchable pinning sites. Pinning strengths of at least 650 Oe can be readily achieved, enough to bring to a standstill domain walls travelling at speeds of at least similar to 20 m s(-1). We exploit this new magneto-ionic effect to demonstrate a prototype non-volatile memory device in which voltage-controlled domain wall traps facilitate electrical bit selection in a magnetic nanowire register.