Majorana modes are zero-energy excitations of a topological superconductor that exhibit non-Abelian statistics(1-3). Following proposals for their detection in a semiconductor nanowire coupled to an s-wave superconductor(4,5), several tunnelling experiments reported characteristic Majorana signatures(6-11). Reducing disorder has been a prime challenge for these experiments because disorder can mimic the zero-energy signatures of Majoranas(12-16), and renders the topological properties inaccessible(17-20). Here, we show characteristic Majorana signatures in InSb nanowire devices exhibiting clear ballistic transport properties. Application of a magnetic field and spatial control of carrier density using local gates generates a zero bias peak that is rigid over a large region in the parameter space of chemical potential, Zeeman energy and tunnel barrier potential. The reduction of disorder allows us to resolve separate regions in the parameter space with and without a zero bias peak, indicating topologically distinct phases. These observations are consistent with the Majorana theory in a ballistic system(21), and exclude the known alternative explanations that invoke disorder(12-16) or a nonuniform chemical potential(22,23).