Iron phosphides with significant variations of Cr (up to 18 wt%) and V (up to 8.6 wt%) contents were detected in gehlenite-bearing breccia at the Hatrurim Complex, Negev desert, Israel. Investigations of the composition and structure of the Fe2P phosphides showed that when the V+Cr content is higher than 0.26 apfu (atoms per formula unit), a transition from the hexagonal barringerite (P62m) to orthorhombic allabogdanite (Pnma) takes place. According to the experimental data, allabogdanite is a high-pressure (>8 GPa) polymorph of barringerite. Pseudowollastonite associated with Cr-V-bearing allabogdanite is an indicator of phosphide crystallization at high temperature (>1200 °C) and low pressure. Thus, at the low pressure close to ambient, when more than 13 at% Fe in Fe2P is substituted by Cr and V, the ortho-rhombic polymorph is stable. The orthorhombic phosphide with the highest Cr and V contents belongs to the andreyivanovite species with the FeCrP end-member formula. This is the first finding on Earth of that very rare mineral described from the Kaidun meteorite. Some Cr-V-bearing phosphides have an unusual morphology, which cannot be explained by crystallization from a melt. More probably, these phosphides can form in the process of replacing fish bone remains. We believe that sedimentary protolith was not thermally altered and contained a significant amount of bituminous organic matter and phosphorite inclusions. Injecting paralava into the sedimentary rocks determines the conditions for phosphide formation on the boundary of these rocks as a result of the high-temperature carbothermal reduction process.