Designing the next generation of corrosion resistant alloys will rely, in part, on developing a better understanding of how to favor the formation of protective surface oxide films in chemically aggressive environments. In this work, we examined the early stages of oxygen adsorption on Ni (111) in the presence of chloride, a known corrosive agent. The analysis was accomplished from first principles via the construction of a database of density functional theory (DFT) calculations which was then used to fit a cluster expansion model Hamiltonian. DFT calculations showed that the face centered cubic (fcc) sites were most stable for adsorption of both chloride and oxygen in agreement with the literature. Hence, only adsorption to the fcc sites was considered in the cluster expansion and the DFT database. The potential function was constructed with the aid of a genetic algorithm (GA) which helped with the selection of appropriate clusters from a candidate pool of figures. The potential function that was developed contained a total of 50 coupled (i.e. Cl-O) and non-coupled (i.e. Cl-Cl and O-O) clusters and was reasonably good at predicting DFT results with a leave-one-out cross validation score of 28.6 meV/site. The potential function was then used to perform a systematic and efficient calculation of the adsorption isotherms of oxygen and chloride at 300 K. It was observed that relatively large chloride chemical potentials were required to displace adsorbed oxygen. Furthermore, the chloride adsorption isotherms indicated a rapid shift between 0.6 ML and 1 ML. This transition was explained by the need for a large chloride chemical potential to overcome the repulsive forces between the chloride adatoms. (c) 2018 The Electrochemical Society.