Fuel injection during negative valve overlap offers a promising method of controlling HCCI combustion, but sorting out the thermal and chemical effects of NVO fueling requires knowledge of temperatures throughout the cycle. Computing bulk temperatures throughout closed portions of the cycle is relatively straightforward using an equation of state, once a temperature at one crank angle is established. Unfortunately, computing charge temperatures at intake valve closing for NVO operation is complicated by a large, unknown fraction of residual gases at unknown temperature. To address the problem, we model blowdown and recompression during exhaust valve opening and closing events, allowing us to estimate in-cylinder charge temperatures based on exhaust-port measurements. This algorithm permits subsequent calculation of crank-angle-resolved bulk temperatures and residual gas fraction over a wide range of NVO operation. Validation methods are employed to assess both accuracy and precision of the temperature calculations. Measured iso-octane ignition temperatures and combustion phasing sensitivity are compared with published experimental trends. Computed bulk temperatures throughout the main compression stroke are compared with core temperature measurements using tracer-based laser-induced fluorescence imaging. For a range of motored and fired operating conditions, computed temperatures are also validated using a 1-D full-engine model. The algorithm-computed temperatures follow trends closely in all validation tests lending confidence in its intended use as a tool for analyzing NVO-HCCI combustion.