Quantum many-body scar states are exceptional finite energy density eigenstates in an otherwise thermalizing system that do not satisfy the eigenstate thermalization hypothesis. We investigate the fate of exact many-body scar states under perturbations. At small system sizes, deformed scar states described by perturbation theory survive. However, we argue for their eventual thermalization in the thermodynamic limit from the finite-size scaling of the off-diagonal matrix elements. Nevertheless, we show numerically and analytically that the nonthermal properties of the scars survive for a parametrically long time in quench experiments. We present a rigorous argument that lower-bounds the thermalization time for any scar state as $t^{*} sim O(lambda^{-1/(1+d)})$, where $d$ is the spatial dimension of the system and $lambda$ is the perturbation strength.