A novel traveling-wave Zeeman decelerator based on a double-helix coil geometry capable of decelerating paramagnetic molecules with high efficiency is presented. Moving magnetic traps are generated by applying time-dependent currents through the decelerator coils. Paramagnetic molecules in low-field-seeking Zeeman states are confined inside the moving traps which are decelerated to lower forward velocities. As a prototypical example, we demonstrate the deceleration of OH radicals from an initial velocity of 445 m/s down to various final velocities. The experimental results are analyzed and numerically reproduced with the help of trajectory simulations confirming the phase-space stability and efficiency of the deceleration of the molecules in the new device.