Faits: A. H.X._ et F.X._ sont depuis le 1er août 1996 locataires d'un appartement de cinq pièces ainsi que d'un box sis dans un immeuble à Genève appartenant à Y._ SA. Le dernier loyer est de 15'804 fr. par an, charges non comprises. Le 11 novembre 2002, les locataires ont informé la bailleresse qu'ils avaient sous-loué l'appartement à A._ aux mêmes conditions que celles du bail principal. La bailleresse a donné son accord, à condition que la sous-location soit de durée déterminée et qu'elle ne débouche pas sur un transfert de bail. A partir du 1er juillet 2007, les locataires ont sous-loué l'appartement à B._ et C._, toujours aux mêmes conditions que celles du bail principal. Le contrat de sous-location a été conclu pour une durée d'une année, tacitement renouvelable d'année en année. La bailleresse n'en a pas été informée. Interpellés le 25 janvier 2010 sur la date de leur retour dans l'appartement, les locataires ont déclaré qu'ils n'avaient plus l'intention de réintégrer les locaux et qu'ils souhaitaient transférer le bail aux sous-locataires. La bailleresse a alors invité les locataires à résilier le contrat, sous menace de procéder elle-même à la résiliation. B. Par avis officiels du 13 avril 2010, la bailleresse a résilié le contrat de bail pour le 31 août 2010. Les locataires ont saisi la Commission de conciliation en matière de baux et loyers du canton de Genève, laquelle a déclaré le congé valable. L'affaire a été portée devant le Tribunal des baux et loyers. Les locataires ont requis la suspension de la procédure jusqu'à ce que les sous-locataires puissent occuper l'appartement qu'ils s'étaient acheté. Sur le fond, les locataires ont conclu à l'annulation du congé et subsidiairement à une prolongation de bail pour quatre ans. Par jugement du 22 novembre 2011, le Tribunal a refusé de suspendre la procédure, a déclaré le congé valable et a refusé toute prolongation du bail. Les locataires ont interjeté appel. Par arrêt du 21 mai 2012, la Chambre des baux et loyers de la Cour de justice a rejeté l'appel et confirmé le jugement attaqué. C. Par-devant le Tribunal fédéral, les locataires (ci-après: les recourants) interjettent un recours en matière civile, à défaut un recours constitutionnel subsidiaire. Ils concluent principalement à l'annulation du congé, subsidiairement à une prolongation du bail de quatre ans. Y._ SA (ci-après: l'intimée) conclut au rejet. Par ordonnance du 11 juillet 2012, la présidente de la cour de céans a accordé l'effet suspensif requis par les recourants. 