The projected entangled pair state (PEPS) ansatz can represent a thermal state in a strongly correlated system. We introduce a variational algorithm to optimize this tensor network whose essential ingredient is an auxiliary tree tensor network (TTN). Since the full tensor environment is taken into account, with increasing bond dimension the PEPS-TTN ansatz provides the exact Gibbs state. Our presentation opens with a 1D version for a matrix product state (MPS-TTN) and then generalizes to PEPS-TTN in 2D. Benchmark results in the quantum Ising model are presented.