Sachverhalt: A. A.a. Die C._ AG (Vermieterin, Beklagte, Beschwerdegegnerin) erwarb am 6. Dezember 2001 die aneinander grenzenden Liegenschaften Strasse U._ und Strasse V._ in Zürich. Der Kaufpreis betrug Fr. 21'529'000.--. Im Jahre 2012 baute die Vermieterin die beiden Liegenschaften um, wofür sie der Generalunternehmerin Fr. 7'007'960.-- bezahlte; für Zusatzarbeiten leistete sie überdies noch Fr. 896'372.--. Nach dem Umbau wiesen die beiden Liegenschaften insgesamt 4'027 m2 Laden-, Restaurations-, Büro-, Lager-, Werkstatt- und Wohnräume auf. Unter anderem sind im Dachstock der beiden Liegenschaften insgesamt sechs 3.5-Zimmer-Maisonette-Wohnungen neu eingebaut worden. A.b. Am 20. März 2013 schlossen A._ (Mieter 1, Kläger 1, Beschwerdeführer 1) und B._ (Mieter 2, Kläger 2, Beschwerdeführer 2) mit der Vermieterin einen Vertrag über die Miete einer der 3.5-Zimmer-Maisonette-Wohnungen im Dachstock der Liegenschaft Strasse U._ in Zürich. Der Mietzins wurde auf Fr. 3'900.-- zuzüglich Fr. 300.-- Nebenkosten à-conto pro Monat festgesetzt. Die Mieter verpflichteten sich überdies, eine Sicherheit von Fr. 12'600.-- zu leisten. Als Mietbeginn wurde der 1. April 2013 festgelegt. Die Mieter arbeiteten beide bei einer Bank in Genf und wurden nach Zürich versetzt. Sie verdienten im Jahr 2013 netto knapp Fr. 80'000.-- bzw. Fr. 100'000.-- und mieteten die Wohnung ab Arbeitsantritt des Mieters 1 gemeinsam, um sich die Kosten zu teilen; der Mieter 2 hatte zuvor in Zürich seit August 2012 ein möbliertes Studio gemietet. B. B.a. Mit Eingabe vom 23. April 2013 gelangten die Mieter an die Schlichtungsbehörde Zürich mit dem Antrag, es sei der Anfangsmietzins für missbräuchlich zu erklären und um Fr. 1'100.-- herabzusetzen. Die Schlichtungsstelle stellte mangels Einigung am 26. August 2013 die Klagebewilligung aus. B.b. Die Mieter gelangten noch am gleichen Tag an das Mietgericht und stellten mit den in der Folge modifizierten Rechtsbegehren schliesslich die Anträge, es sei der Anfangsmietzins für die 3.5-Zimmer-Maisonette-Wohnung als missbräuchlich zu erklären, soweit er monatlich netto Fr. 2'200.-- übersteigt; die hinterlegte Mietzinsgarantie sei auf Fr. 6'600.-- zu reduzieren. Mit Urteil vom 16. Juni 2015 wies das Mietgericht Zürich die Klage ab. Das Mietgericht erwog zunächst, dass die Voraussetzungen für eine Anfechtung des Anfangsmietzinses wegen der Verhältnisse auf dem örtlichen Markt für Wohnräume gemäss Art. 270 Abs. 1 lit. a OR (trotz in der Begründung vorgebrachter Vorbehalte) gegeben seien, weshalb letztlich offen bleiben könne, ob auch eine persönliche Notlage der Mieter vorgelegen habe. Das Gericht kam jedoch zum Schluss, den Mietern sei der ihnen obliegende Nachweis nicht gelungen, dass die Vermieterin einen übersetzten Ertrag aus der Mietwohnung erziele. B.c. Das Obergericht des Kantons Zürich wies mit Urteil vom 9. November 2015 die Berufung der Mieter ab und bestätigte das erstinstanzliche Urteil. Zur Begründung führte das Obergericht aus, es genüge für die Anfechtung des Anfangszinses nach Art. 270 Abs. 1 lit. a OR nicht, wenn der Mieter eine Notlage oder eine Wohnungsnot nachweise; er müsse vielmehr beweisen, dass er sich aus diesem Grund in einer Zwangslage befunden habe, und er müsse nachweisen, dass ihm eine vernünftige Alternative gefehlt habe, wozu er Suchbemühungen nachzuweisen habe. Dass er diesen Nachweis zu erbringen habe, entspreche der Praxis des zürcherischen Obergerichts, die nach dessen Ansicht vom Bundesgericht bestätigt worden sei, das dann aber im Widerspruch dazu entschieden habe, es verletze Bundesrecht, bei Wohnungsnot vom Mieter den Nachweis von Suchbemühungen zu verlangen. Das Obergericht schloss, die Kläger seien zum Nachweis der Missbräuchlichkeit des Anfangsmietzinses nicht zuzulassen, da sie eine Zwangslage nicht nachgewiesen hätten. C. Mit Beschwerde in Zivilsachen vom 15. Dezember 2015 beantragen die Mieter dem Bundesgericht, das Urteil des Obergerichts des Kantons Zürich vom 8. November 2015 sei aufzuheben und das Verfahren sei zum Entscheid über die Missbräuchlichkeit des Anfangsmietzinses an die Vorinstanz zurückzuweisen, eventualiter sei der Anfangsmietzins für missbräuchlich zu erklären, soweit er monatlich netto Fr. 2'200.-- übersteigt, und die Mietkaution sei entsprechend zu reduzieren. Die Beschwerdeführer rügen die Verletzung von Art. 270 Abs. 1 lit. a OR. Zur Begründung des Eventualantrages kritisieren sie die Erwägungen des erstinstanzlichen Mietgerichts. Die Beschwerdegegnerin beantragt in ihrer Vernehmlassung die Abweisung der Beschwerde. Die Vorinstanz hat auf Vernehmlassung verzichtet.