The quest for realization of non-Abelian phases of matter, driven by their possible use in fault-tolerant topological quantum computing, has been spearheaded by recent developments in p-wave superconductors. The chiral p(x)+ip(y)-wave superconductor in two-dimensions exhibiting Majorana modes provides the simplest phase supporting non-Abelian quasiparticles and can be seen as the blueprint of fractional topological order. Alternatively, Kitaev's Majorana wire has emerged as an ideal toy model to understand Majorana modes. Here we present a way to make the transition from Kitaev's Majorana wires to two-dimensional p-wave superconductors in a system with cold atomic gases in an optical lattice. The main idea is based on an approach to generate p-wave interactions by coupling orbital degrees of freedom with strong s-wave interactions. We demonstrate how this design can induce Majorana modes at edge dislocations in the optical lattice, and we provide an experimentally feasible protocol for the observation of the non-Abelian statistics.