In the matrix quantum mechanics (MQM) dual to the non-supersymmetric 2d black hole, we identify a set of degenerate states as the black hole microstates. At leading order in large $N$, the log of number of these states (already calculated by Gross and Klebanov) matches the Bekenstein-Hawking entropy formula, and also agrees with one of two candidates found by Kazakov and Tseytlin. The mass term in Kazakov and Tseytlin’s free energy also matches the energy of these states conjectured by Gross and Klebanov; we show this conjecture. We also calculate the microcanonical entropy in a higher-energy phase, which we conjecture to be dual to the $c = 0$ phase of 2d string theory. We try to interpret our results in string theoretic terms and find that it is consistent with some arguments of Kogan, Sathiapalan and Atick and Witten regarding the phase structure of string theory. Finally, we discuss a tantalising analogy to Motzkin walk models.