Perpendicularly magnetized materials have attracted tremendous interest due to their high anisotropy, which results in extremely narrow, nano-sized domain walls. As a result, the recently studied current-induced domain wall motion (CIDWM) in these materials promises to enable a novel class of data, memory, and logic devices. In this letter, we propose the spin Hall effect as a radically new mechanism for CIDWM. We are able to carefully tune the net spin Hall current in depinning experiments on Pt/Co/Pt nanowires, offering unique control over CIDWM. Furthermore, we determine that the depinning efficiency is intimately related to the internal structure of the domain wall, which we control by small fields along the nanowire. This new manifestation of CIDWM offers a very attractive new degree of freedom for manipulating domain wall motion by charge currents, and sheds light on the existence of contradicting reports on CIDWM in perpendicularly magnetized materials.