Evolutionary searches are used to explore stable Cd–O compounds at ambient pressure. New cubic thermodynamically stable phase CdO2 with space group Pa3 is obtained. Two metastable compounds: zinc-blende and wurtzite phases of CdO have been discovered at ambient pressure. Elastic constants and phonon show that Pa3, zinc-blende and wurtzite structures are mechanically and dynamically stable. Zinc-blende and wurtzite phases are semiconducting with a direct band gap (Γ–ΓΓ–Γ) of 0.89 eV and 0.97 eV respectively.