In the present work, we perform a systematic investigation on p-type codoping in (Ga,Mn)As. Through gradually increasing Zn doping concentration, the hole concentration increases, which should theoretically lead to an increase of the Curie temperature (TC) according to the p-d Zener model. Unexpectedly, although the film keeps its epitaxial structure, both TC and the magnetization decrease. The samples present a phase transition from ferromagnetism to paramagnetism upon increasing hole concentration. In the intermediate regime, we observe a signature of antiferromagnetism. By using channeling Rutherford backscattering spectrometry and particle-induced x-ray emission, the substitutional Mn atoms are observed to shift to interstitial sites, while more Zn atoms occupy Ga sites, which explains the observed behavior. This is also consistent with first-principles calculations, showing that the complex of substitutional Zn and interstitial Mn has the lowest formation energy.