We explore some of the properties of static and stationary solutions of the Einstein-Yang-Mills (EYM) equations. The EYM system has been studied for over 15 years, yielding many surprises along the way. We will review the current state of knowledge of soliton and black hole solutions in asymptotically flat space, where there is a counter-example for each step in the classic uniqueness proof for the Kerr-Newman metric in Einstein-Maxwell theory. We will then discuss recent work on EYM with a negative cosmological constant, where the space of solutions is even richer. We will also describe how the isolated horizons formalism describes the asymptotically flat EYM black holes, and outline how an analogous description might be developed for asymptotically anti-de Sitter EYM black holes.