We consider two-dimensional Yang-Mills theories on arbitrary Riemann surfac
es. 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-di
mensional 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.