Faits: Faits: A. Le 1er décembre 1995, l'assurance Y._, a remis à bail aux époux X._ un appartement de six pièces sis à Genève. Le loyer mensuel était de 3'299 fr. charges comprises. Par courrier du 19 novembre 2001, les époux X._ ont sollicité l'accord de la régie en charge de l'immeuble pour sous-louer l'appartement à B._. Le lendemain, celle-ci a répondu qu'elle attendait que le candidat s'inscrive et remette les documents nécessaires, ce qui a été fait le 29 novembre 2001. Le 27 novembre 2001, les époux X._ ont encore précisé qu'ils seraient absents de Genève durant quelques années, mais souhaitaient ensuite reprendre l'appartement dans lequel ils avaient engagé des frais d'aménagement importants. Le sous-loyer serait le même que celui du bail principal. Le 2 janvier 2002, le contrat de sous-location entre les époux X._ et B._ a été transmis à la régie. Il indiquait un loyer mensuel de 3'299 fr. charges comprises. Le 14 janvier 2002, la régie a répondu qu'elle ne pouvait accéder à la demande de sous-location. Le 2 janvier 2002, le contrat de sous-location entre les époux X._ et B._ a été transmis à la régie. Il indiquait un loyer mensuel de 3'299 fr. charges comprises. Le 14 janvier 2002, la régie a répondu qu'elle ne pouvait accéder à la demande de sous-location. B. Le 1er mars 2002, les époux X._ ont saisi la Commission de conciliation en matière de baux et loyers du canton de Genève d'une requête tendant à ce qu'il soit constaté que le refus de la bailleresse à la sous-location était injustifié. Le 8 mars 2002, la régie a indiqué qu'elle refusait de donner son accord à la sous-location dès lors qu'un "pas-de-porte" de 15'000 fr. était demandé, ce qui rendait la sous-location abusive. Elle a précisé que si les époux X._ passaient outre l'interdiction de sous-louer, le bail serait résilié. En cours de procédure, la bailleresse a encore expliqué qu'elle avait appris l'existence d'un "pas-de-porte" en lisant une annonce relative à l'appartement parue dans la Tribune de Genève du 30 octobre 2001. Elle a en outre contesté que les conditions réelles de la sous-location soient celles figurant sur le bail qui lui avait été communiqué. Au début du mois de mai 2002, B._ a pris possession de l'appartement litigieux. Entendu comme témoin, il a indiqué payer un loyer mensuel de 3'299 fr. charges comprises et avoir acheté aux époux X._, après la signature du bail, mais avant la mise à disposition des locaux, diverses installations pour 8'600 fr. et des meubles pour 27'000 fr. Le dossier comporte deux décomptes, non datés, portant la signature de B._ et celle de sieur X._. Les époux X._ ont produit les factures se rapportant aux meubles et installations cédés. Par avis officiels du 19 septembre 2002, la bailleresse a résilié le bail des époux X._ pour le 31 octobre 2002 en indiquant comme motif: "résiliation fondée sur l'art. 257f al. 3 CO - sous-location illicite". Les avis de résiliation étaient adressés à l'ASLOCA. Les époux X._ ont contesté la validité du congé en faisant valoir sa nullité du fait qu'il était adressé au domicile élu, subsidiairement son inefficacité dès lors que la sous-location était valable. Pour sa part, la bailleresse a initié une procédure en évacuation des époux X._. Par ordonnance du 10 mars 2003, les causes en constatation du caractère injustifié du refus à la sous-location et celle en contestation de la validité du congé ont été jointes et l'instruction de la requête en évacuation a été suspendue jusqu'à droit jugé sur celles-ci. Le 25 mars 2003, la bailleresse a de nouveau fait notifier aux locataires, à leur domicile à Zoug, une résiliation avec effet au 31 mai 2003. Le frère de dame X._ a expliqué qu'il s'était chargé de la sous-location de l'appartement à la demande de sa soeur qui se trouvait en Espagne. Il avait pris l'initiative de rédiger l'annonce parue dans la Tribune de Genève en octobre 2001, en fixant le loyer à 3'500 fr. et en mentionnant une reprise de 15'000 fr. Sa soeur lui avait précisé qu'elle n'entendait pas faire de l'argent avec la sous-location. Elle lui avait encore indiqué qu'elle souhaitait vendre une partie de l'agencement qu'elle avait acheté pour environ 12'000 fr. Par jugement du 13 septembre 2005, le Tribunal des baux et loyers a constaté que la sous-location était valable et que le congé notifié aux époux X._ était inefficace. Saisie par la bailleresse et statuant par arrêt du 18 mai 2006, la Chambre d'appel en matière de baux et loyers a annulé le jugement susmentionné et dit que les avis de résiliation notifiés le 25 mars 2003 avec effet au 31 mai 2003 étaient valables. Appliquant l'art. 271a al. 1 let. a CO, qui prévoit l'annulabilité du congé donné par le bailleur parce que le locataire fait valoir de bonne foi des prétentions découlant du bail, elle a remarqué qu'il convenait d'examiner si les époux X._ avaient le droit de sous-louer et, le cas échéant, s'ils avaient exercé leur droit conformément aux règles de la bonne foi. A cet égard, elle a considéré qu'en tant que tel, le montant du loyer n'était pas abusif. Il apparaissait toutefois que les époux X._ avaient obtenu, pour la vente de leurs propres meubles et les installations qu'ils avaient posées, un prix largement supérieur à ce qu'ils auraient pu obtenir sans la promesse de conclusion du sous-bail. On s'étonnait en effet à la lecture de la liste des meubles et installations vendus de certains postes (disperseur luminé pour 11 fr. 45, porte verres à dents et crochets bains pour 48 fr. 35) ainsi que du montant de certains postes (1'757 fr. pour un canapé blanc acheté 2'800 fr. sept ans plus tôt). Par ailleurs, l'annonce parue dans la Tribune de Genève mentionnait clairement que l'appartement était à louer, moyennant une "reprise d'agencement" pour 15'000 fr. Ainsi, le sous-locataire n'avait d'autre choix, s'il voulait occuper les locaux, que d'accepter la reprise des meubles et des installations. L'art. 254 CO disposait que les transactions couplées avec le bail sont nulles lorsque la conclusion du bail en dépend. La succession des événements montrait que les parties au contrat de sous-location avaient convenu de lier la conclusion du bail à la vente des meubles et installations. En effet, le sous-locataire avait manifesté son intérêt après avoir pris connaissance de l'annonce parue dans la presse, laquelle mentionnait l'exigence d'une reprise. Par la suite, le paiement convenu était intervenu après la signature du sous-bail, mais juste avant la remise des clés de l'appartement. Dès lors que le sous-bail n'aurait pas été conclu si le sous-locataire n'avait pas repris les meubles et installations, il fallait en conclure que les conditions de la location étaient abusives. La vente du mobilier et des installations tendait également à démontrer que les locataires principaux n'avaient pas véritablement l'intention de réintégrer l'appartement litigieux. Certes, deux témoins avaient déclaré que les locataires, à tout le moins dame X._, qui avait de la famille à Genève, avaient l'intention de revenir dans cette ville. L'on ne comprenait toutefois pas pour quelle raison, si telle était effectivement l'intention de celle-ci, elle aurait vendu l'intégralité des meubles et installations qui garnissaient son appartement. Enfin, le montant total de 35'000 fr. pour la reprise de ceux-ci ne pouvait raisonnablement être amorti qu'après une relativement longue période, en tous cas supérieure à quatre ans, même en tenant compte d'un supplément de loyer pour la mise à disposition de mobilier. Or, le sous-locataire avait conclu le bail pour une année et avait déclaré n'avoir l'intention de rester dans l'appartement que pour une durée (jusqu'en septembre 2004, voire début 2005) incompatible avec une période d'amortissement économiquement raisonnable. Au vu de l'ensemble des éléments, les conditions de la sous-location étaient abusives au sens de l'art. 262 al. 2 let. b CO et la bailleresse était ainsi en droit de la refuser. Les intimés avaient fait valoir, en première instance, que si le refus de la sous-location devait être considéré comme étant justifié, la résiliation donnée en application de l'art. 257f al. 3 CO n'était pas valable, faute d'avoir été précédée d'une mise en demeure, d'une part, et faute d'avoir été notifiée à leur domicile, d'autre part. La première notification de la résiliation, adressée à l'ASLOCA, ne pouvait être considérée comme valable. La première résiliation avait en effet été adressée à l'ASLOCA et non au domicile des locataires. Elle indiquait comme motif "résiliation fondée sur l'art. 257f al. 3 CO - sous location illicite". La seconde indiquait le même motif et avait été adressée au domicile des époux X._ le 25 mars 2003, mettant un terme au contrat de bail le 31 mai 2003. L'éventuel vice dans la notification avait ainsi été réparé. En l'espèce, la bailleresse s'était opposée le 14 janvier 2002 à la sous-location, soit avant que celle-ci commence. Elle avait encore indiqué le 8 mars 2002 que si les locataires louaient l'appartement contre sa volonté, le bail serait résilié. Il y avait donc deux protestations écrites claires de la part de la bailleresse, de sorte que celle-ci pouvait procéder à la résiliation du bail en application de l'art. 257f al. 3 CO. La bailleresse avait au demeurant maintenu sa position tout au long de la procédure. En l'espèce, la bailleresse s'était opposée le 14 janvier 2002 à la sous-location, soit avant que celle-ci commence. Elle avait encore indiqué le 8 mars 2002 que si les locataires louaient l'appartement contre sa volonté, le bail serait résilié. Il y avait donc deux protestations écrites claires de la part de la bailleresse, de sorte que celle-ci pouvait procéder à la résiliation du bail en application de l'art. 257f al. 3 CO. La bailleresse avait au demeurant maintenu sa position tout au long de la procédure. C. Parallèlement à un recours en réforme, les époux X._ (les recourants) interjettent un recours de droit public au Tribunal fédéral. Invoquant l'art. 9 Cst., ils concluent à l'annulation de l'arrêt entrepris et au déboutement de leur adverse partie de toutes autres conclusions, avec suite de frais et dépens. L'assurance Y._ (l'intimée) propose le rejet du recours et le déboutement des recourants de toutes autres conclusions, sous suite de frais et dépens. Pour sa part, la cour cantonale se réfère aux considérants de son arrêt quant au fond.