The Initial-Boundary Value Problem for the heat equation is solved by using a new algorithm based on a random walk on heat balls. Even if it represents a sophisticated generalization of the Walk on Spheres (WOS) algorithm introduced to solve the Dirich-let problem for Laplaces equation, its implementation is rather easy. The definition of the random walk is based on a new mean value formula for the heat equation. The convergence results and numerical examples permit to emphasize the efficiency and accuracy of the algorithm.