The threshold properties of photonic crystal quantum dot lasers operating in the slow-light regime are investigated experimentally and theoretically. Measurements show that, in contrast to conventional lasers, the threshold gain attains a minimum value for a specific cavity length. The experimental results are explained by an analytical theory for the laser threshold that takes into account the effects of slow light and random disorder due to unavoidable fabrication imperfections. Longer lasers are found to operate deeper into the slow-light region, leading to a trade-off between slow-light induced reduction of the mirror loss and slow-light enhancement of disorder-induced losses.