We introduce the quantum stochastic walk (QSW), which determines the evolution of generalized quantum mechanical walk on a graph that obeys a quantum stochastic equation of motion. Using an axiomatic approach, we specify the rules for all possible quantum, classical and quantum-stochastic transitions of a vertex as defined from its connectivity. We show how the family of possible QSW encompasses both the classical random walk (CRW) and the quantum walks (QW) as special cases, but also includes more general probability distributions. As an example, we study the QSW on the line, its QW to CRW transition and transitions to genearlized QSWs that go beyond the CRW and QW. QSWs provide a new framework to the study of quantum walks with environmental effects as well as quantum algorithms.