An optimal design methodology is developed in this paper for fuel cell hybrid electric vehicles (FCHEV) based on ordinal optimization (OO) and dynamic programming (DP); the optimal design aims to determine the appropriate sizes of the hydrogen tank, fuel cell, battery, and motor for the purpose of minimizing investment and operational cost given some specification of the car range, the road type and its gradeability. The DP simulates the operation of the vehicle for a set of specified components' sizes for given driving cycles and provides the total vehicle cost per year. The OO method offers an efficient approach for optimization by focusing on ranking and selecting a finite set of “good enough” alternatives through two models: a simple model and an accurate model. The OO program uses the specified sizes of the components that uniformly sample the search space and evaluates these designs using a simple but fast model. As per OO theory, the evaluated designs are sorted in an ascending order and the top-s design solutions are selected. An ordered performance curve method is used to determine the size of the top-s set of “good enough” designs which are then evaluated using an “accurate model” in a kind of horse race. This model is implemented by taking the whole of the driving cycles and an increased number of states in the dynamic programming solution. In these runs the effect of varying the fuel cell, the battery, and hydrogen costs are investigated; car design results are presented with different optimal sizes for different specifications.