In 2008 the Phoenix Mars lander Wet Chemistry Laboratory (WCL) measured 0.6wt% of perchlorate (ClO4-) in the martian soil. A crucial question remaining unanswered is the identity of the parent salt phase(s) of the ClO4 Due to the ClO4- ion's high solubility and stability, its distribution, chemical forms, and interactions with water, could reveal much about the aqueous history of the planet. Until now, the presence of Ca(ClO4)2 as a parent salt has been considered unlikely because based on its eutectic point and model calculations, highly insoluble calcium carbonates and sulfates would serve as sinks for Ca2+ rather than Ca(ClO4)2. Thus, the dominant ClO4- parent salt has been assumed to be a hydrated form of Mg(ClO4)2. Here we report on the results of a new refined analysis of the Phoenix WCL sensor data, post-flight experiments run on a flight-spare WCL unit, and numerous laboratory analyses. The results show that the response of the Ca2+ sensor is extremely sensitive to the counter ion of the ClO4- salt, and that addition of martian soil to the Phoenix WCL that contained only Mg(ClO4)2 or Ca(ClO4)2 would have produced a very different response than what was observed on Mars. A series of analyses were run with Ca2+ sensors and calibration solutions identical to those used on Phoenix, and with a Mars simulant formulation known to give the same results as on Mars. The response of the Ca2+ sensor at various ratios of added Mg(ClO4)2 to Ca(ClO4)2 gave the best fit to the Phoenix data with a sample containing ~60% Ca(ClO4)2 and 40% Mg(ClO4)2. These results suggest that the Ca(ClO4)2 in the Phoenix soil has not been in contact with liquid water and thus did not form by evaporation or sublimation processes. Had the highly soluble Ca(ClO4)2 come into contact with liquid water, then the presence of soluble sulfates would have, on evaporation formed only CaSO4. The presence of Ca(ClO4)2 and Mg(ClO4)2 phases at roughly the CaCO3 to MgCO3 ratio suggests that since their production, the ClO4- phases have remained in a severely arid environment, with minimal or no liquid water interaction. The formation of the Ca(ClO4)2 and Mg(ClO4)2 is also consistent with the interaction of atmospherically deposited HClO4 with Ca- and Mg-carbonates and may also contribute to CO2 enrichment of 18O and may contribute in explaining why carbonates on the surface are at much lower levels than expected from an earlier global wet and warm period.