The hybrid combination of superconductors and low-dimensional semiconductors offers a versatile ground for novel device concepts, such as sources of spin-entangled electrons, nanoscale superconducting magnetometers, or recently proposed qubits based on topologically protected Majorana fermions. The underlying physics behind such hybrid devices ultimately rely on the magnetic properties of sub-gap excitations, known as Andreev levels. Here we report the Zeeman effect on the Andreev levels of a semiconductor nanowire quantum dot (QD) strongly coupled to a conventional superconductor. The combination of the large QD g-factor with the large superconductor critical magnetic field allows spin degeneracy to be lifted without suppressing superconductivity. We show that a Zeeman-split Andreev level crossing the Fermi energy signals a quantum phase transition in the ground state of the superconductivity-induced QD, denoting a change in the fermionic parity of the system. This transition manifests itself as a zero-bias conductance anomaly appearing at a finite magnetic field, with properties that resemble those expected for Majorana fermions in a topological superconductor. Although the herein reported zero-bias anomalies do not hold any relation with topological superconductivity, the observed parity transitions can be regarded as precursors of Majorana modes in the long-wire limit. ; Comment: 16 pages, 9 figures