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 .