50 years after the duality of large N gauge theories to string theories was suggested, we still do not have a constructive method to find the string dual of a given gauge theory. I will review work in progress (in collaboration with S. Kundu, T. Sheaffer and L. Yung) on two approaches to understanding this, in what should perhaps be the simplest case, namely two dimensional gauge theories. The first approach uses perturbation theory to obtain an effective stringy description of 2d QCD with very massive adjoint fermions. The second approach starts from finding a good worldsheet description for the string dual to the two dimensional pure Yang-Mills theory.