We examine the problem of counting bound states of BPS black holes on local Calabi-Yau three-folds which are fibrations over a Riemann surface by computing the partition function of q-deformed Yang-Mills theory on the Riemann surface. We consider the genus zero case and we discuss its large N limit that should be related to the topological string partition function, according to the Ooguri-Strominger-Vafa conjecture. We find a peculiar phase structure by explicitly solving the large N saddle-point equations: a third-order phase transition separates a weak-coupling regime, described by topological strings on the resolved conifold, from a strong-coupling region in which the relevant Calabi-Yau geometries and the expected chiral-antichiral dynamics are found. We generalize this result to the pure chiral case where we are able to make an explicit connection with the Gross-Taylor string description of ordinary QCD2, relating Gromov-Witten invariants and Hurwitz numbers. An intriguing observation is that the perturbative topological string expansion appears to diverge at the critical points.