Described are solid-state electrochemical energy storage devices and methods of making solid-state electrochemical energy storage devices in which components of the batteries are truly solid-state and do not comprise a gel. Nor do they rely on lithium-containing electrolytes. Electrolytes useful with the solid-state electrochemical energy storage described herein include, for example, ceramic electrolytes exhibiting a crystal structure including voids or crystallographic defects that permit conduction or migration of oxygen ions across a layer of the ceramic electrolyte. Disclosed methods of making solid-state electrochemical energy storage devices include multi-stage deposition processes, in which an electrode is deposited in a first stage and an electrolyte is deposited in a second stage.