  We calculate the partition function of the $SU(N)$ ( and $U(N)$) generalized
$YM_2$ theory defined on an arbitrary Riemann surface. The result which is
expressed as a sum over irreducible representations generalizes the Rusakov
formula for ordinary YM_2 theory. A diagrammatic expansion of the formula
enables us to derive a Gross-Taylor like stringy description of the model. A
sum of 2D string maps is shown to reproduce the gauge theory results. Maps with
branch points of degree higher than one, as well as ``microscopic surfaces''
play an important role in the sum. We discuss the underlying string theory.
