An Internal Combustion Engine (ICE) under cold conditions experiences increased friction losses due to a high viscosity of the lubricant. With the additional control freedom present in hybrid electric vehicles, the losses during warmup can be minimized and fuel can be saved. In this paper, firstly, a control-oriented model of the ICE, describing the warmup behavior, is developed and validated on measured vehicle data. Secondly, the two-state, non-autonomous fuel optimization, for a parallel hybrid electric vehicle with stop-start functionality, is solved using optimal control theory. The principal behavior of the Lagrange multipliers is explicitly derived, including the discontinuities (jumps) that are caused by the constraints on the lubricant temperature and the energy in the battery system. The minimization of the Hamiltonian for this two-state problem is also explicitly solved, resulting in a computationally efficient algorithm. The optimal controller shows the fuel benefit, as a function of the initial temperature, for a long-haul truck simulated on the FTP-75.