Myosin VI is a molecular motor involved in intracellular vesicle and organelle transport. To carry out its cellular functions myosin VI moves toward the pointed end of actin, backward in relation to all other characterized myosins. Myosin V, a motor that moves toward the barbed end of actin, is processive, undergoing multiple catalytic cycles and mechanical advances before it releases from actin. Here we show that myosin VI is also processive by using single molecule motility and optical trapping experiments. Remarkably, myosin VI takes much larger steps than expected, based on a simple lever-arm mechanism, for a myosin with only one light chain in the lever-arm domain. Unlike other characterized myosins, myosin VI stepping is highly irregular with a broad distribution of step sizes.