A few studies estimating temperature complexity have found decreased Shannon entropy, during severe stress. In this study, we measured both Shannon and Tsallis entropy of temperature signals in a cohort of critically ill patients and compared these measures with the sequential organ failure assessment (SOFA) score, in terms of intensive care unit (ICU) mortality. Skin temperature was recorded in 21 mechanically ventilated patients, who developed sepsis and septic shock during the first 24 h of an ICU-acquired infection. Shannon and Tsallis entropies were calculated in wavelet-based decompositions of the temperature signal. Statistically significant differences of entropy features were tested between survivors and non-survivors and classification models were built, for predicting final outcome. Significantly reduced Tsallis and Shannon entropies were found in non-survivors (seven patients, 33%) as compared to survivors. Wavelet measurements of both entropy metrics were found to predict ICU mortality better than SOFA, according to a combination of area under the curve, sensitivity and specificity values. Both entropies exhibited similar prognostic accuracy. Combination of SOFA and entropy presented improved the outcome of univariate models. We suggest that reduced wavelet Shannon and Tsallis entropies of temperature signals may complement SOFA in mortality prediction, during the first 24 h of an ICU-acquired infection.