We propose to realize a p-wave superfluid using a Bose-Fermi mixture in a two dimensional optical lattice. We find that in presence of a vortex the system admits a zero-energy (Majorana) mode, which could be usefully exploited to realize a Topologically-protected Quantum Computer. The zero-mode is shown to survive even in the experimentally relevant conditions of finite lattices and external trapping. Close to half-filling, this Majorana mode acquires a novel checkerboard structure characterized by d-wave symmetry.