Zeeman fields can drive semiconductor quantum wires with strong spin-orbit coupling and in proximity to s-wave superconductors into a topological phase which supports end Majorana fermions and offers an attractive platform for realizing topological quantum information processing. Here, we investigate how potential disorder affects the topological phase by a combination of analytical and numerical approaches. Most prominently, we find that the robustness of the topological phase against disorder depends sensitively and nonmonotonously on the Zeeman field applied to the wire.