A semiclassical methodology for evaluating the Boltzmann operator entering semiclassical approximations for finite temperature correlation functions is described. Specifically, Miller's imaginary time semiclassical approach is applied to the Herman-Kluk coherent state initial value representation (IVR) for the time evolution operator in order to obtain a coherent state IVR for the Boltzmann operator. The phase-space representation gives rise to exponentially decaying factors for the coordinates and momenta of the real time trajectories employed in the dynamical part of the calculation. A Monte Carlo procedure is developed for evaluating dynamical observables, in which the absolute value of the entire exponential part of the integrand serves as the sampling function. Numerical tests presented show that the methodology is accurate as well as stable over the temperature range relevant to chemical applications.