The cold start of fuel cells limits their wide application. Since the water produced by fuel cells takes up more space when it freezes, it may affect the internal structure of the stack, causing collapse and densification of the pores inside the catalytic layer. This paper mainly analyzes the influence of different startup strategies on the stack cold start, focusing on the change in the stack temperature and the ice volume fraction of the catalytic layer. When designing a startup strategy, it is important to focus not only on the optimization of the startup time, but also on the principle of minimizing the damage to the stack. A lumped parameter cold-start model was constructed, which was experimentally verified to have a maximum error of 8.9%. On this basis, a model predictive control (MPC) algorithm was used to control the starting current. The MPC cold-start strategy reached the freezing point at 17 s when the startup temperature was −10 °C, which is faster than other startup strategies. Additionally, the time to ice production was controlled to about 20 s. Compared with the potentiostatic strategy and maximum power strategy, MPC is optimal and still has great potential for further optimization.