  We extend the results found for Matrix String Theory to Heterotic Matrix
String Theory, i.e. to a 2d O(N) SYM theory with chiral (anomaly free) matter
and N=(8,0) supersymmetry. We write down the instanton equations for this
theory and solve them explicitly. The solutions are characterized by branched
coverings of the basis cylinder, i.e. by compact Riemann surfaces with
punctures. We show that in the strong coupling limit the action becomes the
heterotic string action plus a free Maxwell action. Moreover the amplitude
based on a Riemann surface with p punctures and h handles is proportional to
g^{2-2h-p}, as expected for the heterotic string interaction theory with string
coupling g_s=1/g.
