We have determined experimentally the solubility of iodine in a range of synthetic basaltic (CMAS) liquids. The solubility of iodine ranges from 1.2 × 10 -4 to 2.6 × 10 -3 g/g • atm (0.02 to 0.45 ccSTP/ g • atm) over the range of compositions studied. These values are a few orders of magnitude greater than the solubility of xenon in silicate liquids. This difference in solubility means that iodine will tend to become enhanced relative to xenon in a silicate melt in the process of outgassing. These new results are used to model the early outgassing history of Mars based on I-Xe isotopic systematics. To assess the timing and extent of outgassing that can produce the present-day martian atmosphere, we consider two bracketing scenarios. In both scenarios two stages of outgassing are assumed. The first stage of outgassing results from an early formed magma ocean; the atmosphere outgassed in the first stage is assumed to have been removed by hydrodynamic escape and impact erosion before the second stage of outgassing. The two scenarios differ in the timing of atmospheric removal vis à vis the first (magma ocean) stage of outgassing. We consider a range of starting compositions. It is shown that an early magma ocean on Mars, which outgassed, followed by atmospheric erosion and a second stage of outgassing, can explain the 129 Xe/ 132 Xe ratios for known martian reservoirs. The extent to which Mars is outgassed is subject to wide uncertainty. However, stricter constraints are imposed as the timing of the end of catastrophic atmospheric loss occurs at progressively younger times. These scenarios require a highly energetic late accretionary environment for Mars.