Power source characteristics are changing fast under the “three-highs” background. Massive integration of traditional electric vehicles (EVs) is significantly altering grid operation modes, and leads to frequent large-scale power flow shifts. It also causes traffic congestion and overload problems. These issues threaten grid reliability. Hydrogen is a promising energy carrier and is increasingly advocated to address insufficient energy flexibility in new power systems. This supports the adoption of Fuel Cell Hybrid Electric Vehicles (FCHEVs). It also enhances grid flexibility. This paper proposes an optimal planning framework for cross-energy systems and develops a detailed FCHEV model. The model represents both electrical and hydrogen energy storage in FCHEVs. A stochastic programming-based planning model is constructed. It aims to minimize the total cost of unit commitment and the hydrogen supply chain. Case study shows that FCHEVs can reduce operational costs across energy systems compared to traditional EVs. They also help in accommodating renewable energy.