We define a natural state space and Markov process associated to the stochastic Yang-Mills heat flow in two dimensions. To accomplish this we first introduce a space of distributional connections for which holonomies along sufficiently regular curves (Wilson loop observables) and the action of an associated group of gauge transformations are both well-defined and satisfy good continuity properties. The desired state space is obtained as the corresponding space of orbits under this group action and is shown to be a Polish space when equipped with a natural Hausdorff metric. To construct the Markov process we show that the stochastic Yang-Mills heat flow takes values in our space of connections and use the "DeTurck trick" of introducing a time dependent gauge transformation to show invariance, in law, of the solution under gauge transformations. Our main tool for solving for the Yang-Mills heat flow is the theory of regularity structures and along the way we also develop a "basis-free" framework for applying the theory of regularity structures in the context of vector-valued noise - this provides a conceptual framework for interpreting several previous constructions and we expect this framework to be of independent interest.