This paper investigates the Proton Exchange Membrane Fuel Cell (PEMFC) Cold Startup problem within the specific context of the Plugin Hybrid Electric Vehicles (PHEV). A global strategy which aims at providing an efficient method to minimize the energy consumption during the startup of a PEMFC is proposed. The overall control system is based on a supervisory architecture in which the Energy Management System (EMS) plays the role of the power flow supervisor. The EMS estimates in advance, the time to start the fuel cell (FC) based upon the battery energy usage during the trip. Given this estimation and the amount of additional energy required, the fuel cell temperature management strategy computes the most appropriate time to start heating the stack in order to reduce heat loss through the natural convection. As the cell temperature rises, the PEMFC is started and the reaction heat is used as a self-heating power source to further increase the stack temperature. A time optimal self-heating approach based on the Pontryagin minimum principle is proposed and tested. The experimental results have shown that the proposed approach is efficient and can be implemented in real-time on FC-PHEVs.