Metal oxides are commonly used as electrolytes for redox-based resistive switching memories. In most cases, non-noble metals are directly deposited as ohmic electrodes. We demonstrate that irrespective of bulk thermodynamics predictions an intermediate oxide film a few nanometers in thickness is always formed at the metal/insulator interface, and this layer significantly contributes to the development of reliable switching characteristics. We have tested metal electrodes and metal oxides mostly used for memristive devices, that is, Ta, Hf, and Ti and TaO, HfO, and SiO. Intermediate oxide layers are always formed at the interfaces, whereas only the rate of the electrode oxidation depends on the oxygen affinity of the metal and the chemical stability of the oxide matrix. Device failure is associated with complete transition of short-range order to a more disordered main matrix structure.