We investigate the effect of uniaxial heterostrain on the interacting phase diagram of magic-angle twisted bilayer graphene. Using both self-consistent Hartree-Fock and density-matrix renormalization group calculations, we find that small strain values ($epsilon sim 0.1 - 0.2 %$) drive a zero-temperature phase transition between the symmetry-broken Kramers intervalley-coherent insulator and a nematic semi-metal. The critical strain lies within the range of experimentally observed strain values, and we therefore predict that strain is at least partly responsible for the sample-dependent experimental observations.