Solid oxide fuel cells are attractive devices in a sustainable energy context because of their fuel flexibility and potentially highly efficient conversion of chemical to electrical energy. The performance of the device is to a large extent determined by the atomic structure of the electrode–electrolyte interface. Lack of atomic-level information about the interface has limited the fundamental understanding, which further limits the opportunity for optimization. The atomic structure of the interface is affected by electrode potential, chemical potential of oxygen ions, temperature, and gas pressures. In this paper we present a scheme to determine the metal–oxide interface structure at a given set of these environmental parameters based on quantum chemical calculations. As an illustration we determine the structure of a Ni-YSZ anode as a function of electrode potential at 0 and 1000 K. We further describe how the structural information can be used as a starting point for accurate calculations of the kinetics of fuel oxidation reactions, in particular the hydrogen oxidation reaction. More generally, we anticipate that the scheme will be a valuable theoretical tool to describe solid–solid electrochemical interfaces.