For the first time on Mars, the crystalline magnesium-sulfate mineral starkeyite (MgSO4‧4H2O) was definitively identified using the CheMin X-ray diffraction instrument at Gale crater. At the Canaima drill site, starkeyite along with amorphous MgSO4‧nH2O are among the “polyhydrated Mg-sulfates” interpreted in orbital reflectance spectra. Mg-sulfates are good climate indicators as they are very responsive to changes in temperature and relative humidity. We hypothesize that, through evaporation, Mg-sulfates formed at the end of brine evolution when ion concentrations became saturated and precipitated on the surface or near sub-surface as either epsomite or meridianiite. These minerals were subsequently dehydrated later to starkeyite and amorphous MgSO4‧nH2O in response to a drier Mars. At Canaima, starkeyite is stable and would form during the warmer Mars summers. Due to very slow kinetics at the low Mars winter temperatures, starkeyite and amorphous MgSO4‧nH2O would be resistant to recrystallize to more hydrous forms and thus likely persist year-round. During the course of analyses, starkeyite transforms into amorphous MgSO4‧nH2O inside the rover body due to the elevated temperature and greatly reduced relative humidity compared to the martian surface at the Canaima drill site. It is possible that crystalline sulfate minerals existed in earlier samples measured by CheMin but altered inside the rover before they could be analyzed. Starkeyite is most likely prevalent in the subsurface, whereas both starkeyite and amorphous MgSO4‧nH2O are likely present on the surface as starkeyite could partially transform into amorphous MgSO4‧nH2O due to direct solar heating.