We investigate the heat statistics in a relaxation process of quantum Brownian motion described by the Caldeira-Leggett model. By employing the normal mode transformation and the phase-space formulation approach, we can analyze the quantum heat distribution within an exactly dynamical framework beyond the traditional paradigm of Born-Markovian and weak-coupling approximations. It is revealed that the exchange fluctuation theorem for quantum heat generally breaks down in the strongly non-Markovian regime. Our results may improve the understanding about the nonequilibrium thermodynamics of open quantum systems when the usual Markovian treatment is no longer appropriate.