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.