Faits : A. Par contrat de bail du 20 décembre 1999, B.X._ a remis à bail à Z._, née le 13 mars 1938, un appartement de deux pièces au deuxième étage d'un immeuble à Chêne-Bougeries (Genève), pour une durée d'un an, renouvelable ensuite tacitement d'année en année, avec préavis de résiliation de trois mois, pour un loyer initial, charges comprises, de 1'080 fr. par mois. Tant dans le contrat de bail que dans l'avis de fixation du loyer, la bailleresse est indiquée comme représentée par sa régie. Selon le registre foncier, l'appartement loué appartient en copropriété par moitié à B.X._ et A.X._. B. B.a. Le 18 juin 2013, A.X._, agissant par cette même régie, a résilié le bail pour le 31 décembre 2013, sans indication de motifs. Sous la rubrique " bailleur " de l'avis de résiliation, seul le nom de A.X._ est indiqué; le nom de B.X._ n'apparaît ni dans l'avis, ni dans la lettre d'accompagnement de la régie. Par courrier du 17 juillet 2013, la locataire, par l'intermédiaire de l'Asloca, a demandé à connaître le motif du congé, invoqué la nullité des avis de majoration de loyer de 2007, 2008, 2010 et 2011, demandé le remboursement du trop-perçu qui en résultait et la baisse du loyer à compter du 1er janvier 2014. B.b. La locataire a contesté la résiliation du bail par requête de conciliation du 17 juillet 2013, dirigée contre A.X._ seul et adressée à la Commission de conciliation en matière de baux et loyers du canton de Genève. Elle a conclu à son annulation. La nullité des avis de majoration de loyer, le remboursement du trop-perçu et la réduction du loyer à 1'000 fr. à compter du 1er janvier 2014, ne sont plus litigieux dans la procédure devant le Tribunal fédéral. La conciliation ayant échoué, la locataire a déposé sa demande devant le Tribunal des baux et loyers du canton de Genève le 8 novembre 2013. A.X._ a conclu à la validité de la résiliation. Le Tribunal des baux a, par jugement du 20 mars 2015, notamment déclaré le congé valable (ch. 1) et octroyé à la locataire une unique prolongation de bail de 3 ans jusqu'au 31 décembre 2016 (ch. 2). Statuant le 15 février 2016, la Chambre des baux et loyers de la Cour de justice du canton de Genève a admis l'appel de la locataire, annulé les ch. 1 et 2 du jugement attaqué et constaté la nullité de la résiliation. C. Contre cet arrêt, B.X._ et A.X._ exercent un recours en matière civile au Tribunal fédéral, concluant à ce qu'il soit réformé dans le sens jugé par le Tribunal des baux. Ils invoquent l'établissement manifestement inexact des faits (art. 97 LTF; 9 Cst.) et la violation des art. 32, 266a et 266l CO. L'intimée conclut à l'irrecevabilité et au rejet du recours en tant qu'il constate la nullité et, subsidiairement, conclut à l'annulation de la résiliation et, plus subsidiairement, à ce qu'une prolongation de bail de quatre ans jusqu'au 31 décembre 2017 lui soit accordée, sauf à renvoyer la cause à la Cour de justice pour nouvelle décision sur ces deux derniers points. Les recourants ont déposé des observations complémentaires. La cour cantonale s'est référée aux considérants de son arrêt.