An understanding of the relative stability of surface facets is crucial to develop predictive models of catalyst activity and to fabricate catalysts with a controlled morphology. In this work, we present a systematic density functional theory study of the effect of lattice strain and CO environment on the surface formation energies of Cu, Pt, and Ni. First, we show that both compressive and tensile lattice strains favor the formation of stepped versus low-index terraces such as (111) and (100). Then, we investigate the effect of the CO environment using configurations of CO at various coverages, determined using a greedy, systematic approach, inspired by forward stepwise feature selection. We find that the CO environment favors stepped facets on Ni, Cu, and Pt. These trends are illustrated with the corresponding equilibrium Wulff shapes at various strains and CO pressures. In general, the surface energies of the studied transition metals are highly sensitive to strain and CO coverage, which should be considered when rationalizing trends in the catalytic activity.