We consider two-dimensional Yang-Mills theories on arbitrary Riemann surfaces. We introduce a generalized Yang-Mills action, which coincides with the ordinary one on flat surfaces but differs from it in its coupling to two-dimensional gravity. The quantization of this theory in the unitary gauge can be consistently performed taking into account all the topological sectors arising from the gauge-fixing procedure. The resulting theory is naturally interpreted as a Matrix String Theory, that is as a theory of covering maps from a two-dimensional world-sheet to the target Riemann surface.