Under high pressure, krypton, one of the most inert elements is predicted to become sufficiently reactive to form a new class of krypton compounds; krypton oxides. Using modern ab-initio evolutionary algorithms in combination with Density Functional Theory, we predict the existence of several thermodynamically stable Kr/O species at elevated pressures. In particular, our calculations indicate that at approx. 300 GPa the monoxide, KrO, should form spontaneously and remain thermo- and dynamically stable with respect to constituent elements and higher oxides. The monoxide is predicted to form non-molecular crystals with short Kr-O contacts, typical for genuine chemical bonds.