We present a proof that quantum Yang-Mills theory can be consistently defined as a renormalized, perturbative quantum field theory on an arbitrary globally hyperbolic curved, Lorentzian spacetime. To this end, we construct the non-commutative algebra of observables, in the sense of formal power series, as well as a space of corresponding quantum states. The algebra contains all gauge invariant, renormalized, interacting quantum field operators (polynomials in the field strength and its derivatives), and all their relations such as commutation relations or operator product expansion. It can be viewed as a deformation quantization of the Poisson algebra of classical Yang-Mills theory equipped with the Peierls bracket. The algebra is constructed as the cohomology of an auxiliary algebra describing a gauge fixed theory with ghosts and anti-fields. A key technical difficulty is to establish a suitable hierarchy of Ward identities at the renormalized level that ensure conservation of the interacting BRST-current, and that the interacting BRST-charge is nilpotent. The algebra of physical interacting field observables is obtained as the cohomology of this charge. As a consequence of our constructions, we can prove that the operator product expansion closes on the space of gauge invariant operators. Similarly, the renormalization group flow is proved not to leave the space of gauge invariant operators.