Batteries are useful in Fuel Cell Hybrid Electric Vehicles (FCHEV) to fulfill transient demands and for regenerative braking. Efficient energy management strategies paired with optimal powertrain design further improves the efficiency. In this paper, a new methodology to simultaneously size the propulsive elements and optimize the power-split strategy of a Range Extended Battery Electric Vehicle (REBEV), using a Polymer Electron Membrane (PEM) Fuel Cell, is proposed. Dynamic Programming is used to compute the optimal energy management strategy for a given driving mission profile. The component sizing problem is performed using a machine learning based, guided design space exploration to find the set of Pareto-optimal solutions that give the best trade-offs between the different objectives. The powertrain model includes the dynamic behavior of the fuel cell system compressor and a battery lumped parameter thermal model along with the model of the fuel cell and a zero-order battery model, providing accurate estimates of powertrain performance and component sizing. Effect of the driving mission profile on the extent of hybridization in the powertrain design is also studied.