For dyons in heterotic string theory compactified on a six-torus, with electric charge vector Q and magnetic charge vector P, the positive integer I = g.c.d.(Q wedge P) is an invariant of the U-duality group. We propose the microscopic theory for computing the spectrum of all dyons for all values of I, generalizing earlier results that exist only for the simplest case of I=1. Our derivation uses a combination of arguments from duality, 4d-5d lift, and a careful analysis of fermionic zero modes. The resulting degeneracy agrees with the black hole degeneracy for large charges and with the degeneracy of field-theory dyons for small charges. It naturally satisfies several physical requirements including integrality and duality invariance. As a byproduct, we also derive the microscopic (0,4) superconformal field theory relevant for computing the spectrum of five-dimensional Strominger-Vafa black holes in ALE backgrounds and count the resulting degeneracies.