We study the Einstein-Yang-Mills system in both the Lorenz and harmonic gauges, where the Yang-Mills fields are valued in any arbitrary Lie algebra $\cal G$, associated to any compact Lie group $G$. This gives a system of hyperbolic partial partial differential that does not satisfy the null condition and that has new complications that are not present for the Einstein vacuum equations nor for the Einstein-Maxwell system. We prove the exterior stability of the Minkowski space-time, $\mathbb{R}^{1+3}$, governed by the fully coupled Einstein-Yang-Mills system in the Lorenz gauge, valued in any arbitrary Lie algebra $\cal G$, without any assumption of spherical symmetry. We start with an arbitrary sufficiently small initial data, defined in a suitable energy norm for the perturbations of the Yang-Mills potential and of the Minkowski space-time, and we show the well-posedness of the Cauchy development in the exterior, and we prove that this leads to solutions converging in the Lorenz gauge and in wave coordinates to the zero Yang-Mills fields and to the Minkowski space-time. This provides a first detailed proof of the exterior stability of Minkowski governed by the fully non-linear Einstein-Yang-Mills equations in the Lorenz gauge, by using a null frame decomposition that was first used by H. Lindblad and I. Rodnianski for the case of the Einstein vacuum equations. We note that in contrast to the much simpler case of the Einstein-Maxwell equations where one can omit the potential, in fact in the non-abelian case of the Einstein-Yang-Mills equations, the question of stability, or non-stability, is a purely gauge dependent statement and the partial differential equations depend on the gauge on the Yang-Mills potential that is needed to write up the equations.