This paper defines the criteria under which the early exercise of an American option is never optimal, whether under positive or negative rates, and gives a short analysis of the various shapes of the exercise region under negative interest rates. It then presents a new integral equation, which establishes the option price and the two early-exercise boundaries under negative rates, and shows how to solve this new equation through modifications to the modern and efficient algorithm of Andersen and Lake, from changes in the initial estimate of the two boundaries to the more subtle changes required in their fixed-point method for stability. Finally, the performance and accuracy of the resulting algorithm are assessed against a cutting-edge finite-difference method implementation.