Cr is a critical alloying element in Ni-based alloys. The role of Cr on the formation of oxide nuclei in Ni-Cr alloys is theoretically investigated with density functional theory. Our simulation indicates that Cr has strong binding energy with the nearest oxygen and that it enhances the stability of the metal-oxide nucleus. Therefore, oxide dispersion can be promoted by the incorporation of Cr into Ni alloys. Additionally, potential oxide candidates for the oxide strengthening of Ni-Cr alloys are theoretically explored. The findings, through an analysis of electronic structures, suggest that La and Y are most promising when attempting to realize stable oxide formation in Ni-Cr alloys and reveal that the metal used to create the primary oxides should have low electronegativity and a large atomic radius to create stable metal-oxide nuclei.