Motor proteins are active biological molecules that perform their functions by converting chemical energy into mechanical work. They move unidirectionally along rigid protein filaments or DNA and RNA molecules in discrete steps by hydrolyzing ATP (adenosine triphsophate) or related energy-rich compounds. Recent single-molecule experiments have shown that motor proteins experience significant spatial fluctuations during its motion, leading to broad step-size distributions. The effect of these spatial fluctuations is analyzed explicitly by considering discrete-state stochastic models that allow us to compute exactly all dynamic properties. It is shown that for symmetric spatial fluctuations there is no change in mean velocities for weak external forces, while dispersions and stall forces are strongly affected at all conditions. These results are illustrated by several simple examples. Our method is also applied to analyze the effect of step-size fluctuations on dynamics of myosin V motor proteins. It is argued that spatial fluctuations might be used to control and regulate the dynamics of motor proteins.