Using new XMM and Chandra observations we present an analysis of the temperature structure of the hot gas within a radius of 100 kpc of the bright nearby galaxy group NGC 5044. A spectral deprojection analysis of data extracted from circular annuli reveals that a two-temperature model (2T) of the hot gas is favored over single-phase or cooling flow (M_dot = 4.5 +/- 0.2 M_{sun}/yr) models within the central ~30 kpc. Alternatively, the data can be fit equally well if the temperature within each spherical shell varies continuously from ~T_h to T_c ~ T_h/2, but no lower. The high spatial resolution of the Chandra data allows us to determine that the temperature excursion T_h --> T_c required in each shell exceeds the temperature range between the boundaries of the same shell in the best-fitting single-phase model. This is strong evidence for a multi-phase gas having a limited temperature range. The cooler component of the 2T model has a temperature (T_c ~ 0.7 keV) similar to the kinetic temperature of the stars. The hot phase has a temperature (T_h ~ 1.4 keV) characteristic of the virial temperature of the ~10^{13} M_{sun} halo expected in the NGC 5044 group. However, in view of the morphological disturbances and X-ray holes visible in the Chandra image within R ~10 kpc, bubbles of gas heated to ~T_h in this region may be formed by intermittent AGN feedback. Some additional heating at larger radii may be associated with the evolution of the cold front near R ~50 kpc, as suggested by the sharp edge in the EPIC images.