Sachverhalt:
A.
A._ und B._ (Kläger, Beschwerdeführer) sind seit 1. April 2006 Mieter einer 4-Zimmerwohnung und seit 1. Juni 2013 Mieter eines unmöblierten Mansardenzimmers Nr. 7 an der Strasse U._ in V._. Mit schriftlichem Vertrag vom 13. Januar 2016 überliess die damalige Vermieterin der Beschwerdeführerin 2 das Mansardenzimmer Nr. 8.
Die C._ Anlagestiftung (Beklagte, Beschwerdegegnerin) erwarb per 1. Juli 2016 die Liegenschaft an der Strasse U._. In der Folge lud die Beklagte sämtliche Mieter zu einer Mieterorientierung auf den 27. September 2016 ein, um diese über die von ihr beabsichtigte Totalsanierung zu informieren. Nach durchgeführter Mieterorientierung wandten sich die Kläger mit Schreiben vom 5. Oktober 2016 an die Beklagte. Sie teilten ihr im Wesentlichen mit, um eine Leerkündigung zu vermeiden, könne sich die Mieterschaft vorstellen, während der Umbauphase eine andere Wohnung zu beziehen oder innerhalb der Liegenschaft zu rotieren. Sie selbst seien bereit, ihre Wohnung zeitweilig zu räumen. Die Beklagte erklärte daraufhin in ihrem Antwortschreiben vom 10. Oktober 2016, eine abschliessende Beurteilung der von den Mietern unterbreiteten Vorschläge sei noch nicht möglich, und sie würde die Mieter, wie sie dies an der Mieterorientierung kommuniziert habe, über das Bauvorhaben regelmässig informieren.
Mit Einschreiben vom 28. Februar 2017 kündigte die Beklagte die Mietverträge mittels amtlich genehmigtem Formular per 30. September 2017. Unter Bezugnahme auf die Mieterorientierung vom 27. September 2016 führte sie in ihrer Begründung die geplanten Sanierungsmassnahmen einzeln auf und wies darauf hin, dass der Ausbau des Dachgeschosses sowie die umfassende Innensanierung sich nicht in bewohntem Zustand bewerkstelligen liessen, weshalb sämtliche Mietverhältnisse gekündigt werden müssten.
B.
Dagegen reichten die Kläger mit Eingabe vom 28. August 2017 Klage beim Mietgericht des Bezirksgerichts Zürich ein. Sie beantragten, die angefochtenen Kündigungen für die 4-Zimmerwohnung und die Mansarden Nr. 7 und 8 seien für ungültig zu erklären, soweit sie wirksam seien.
Mit Urteil vom 4. Januar 2018 wies das Mietgericht die Klage ab, stellte die Gültigkeit der Kündigungen der 4-Zimmerwohnung und der Mansarden Nr. 7 und 8 fest und sah von einer Erstreckung der Mietverhältnisse ab.
Gegen das Urteil des Mietgerichts erhoben die Kläger Berufung an das Obergericht des Kantons Zürich. Dieses wies mit Urteil vom 11. Juni 2018 die Berufung ab, soweit es darauf eintrat, und bestätigte das Urteil des Mietgerichts.
C.
Dagegen erhoben die Beschwerdeführer Beschwerde in Zivilsachen an das Bundesgericht. Sie beantragten, in Gutheissung der Beschwerde sei das Urteil des Obergerichts aufzuheben. Die Kündigung für die 4-Zimmerwohnung sei für ungültig zu erklären. Die Mietverhältnisse über die Mansarden Nr. 7 und 8 seien bis zum Beginn der Umbauarbeiten zu erstrecken. Eventualiter sei die Sache im Sinne der Erwägungen an die Vorinstanz zurückzuweisen. Zur Neufestsetzung der Kosten und Entschädigungsfolgen des kantonalen Verfahrens sei die Sache an die Vorinstanz zurückzuweisen. Schliesslich beantragten die Beschwerdeführer, es sei festzustellen, dass der vorliegenden Beschwerde von Gesetzes wegen aufschiebende Wirkung zukomme. Eventualiter sei der Beschwerde die aufschiebende Wirkung zuzuerkennen.
Die Beschwerdegegnerin beantragte die Abweisung der Beschwerde, soweit darauf überhaupt einzutreten sei. Es sei der Beschwerde sodann keine aufschiebende Wirkung zu erteilen. Die Parteien replizierten und duplizierten. Die Vorinstanz verzichtete auf eine Vernehmlassung.

Erwägungen:
1.
Die Sachurteilsvoraussetzungen sind erfüllt und geben zu keinen Bemerkungen Anlass. Unter Vorbehalt einer rechtsgenüglichen Begründung (Art. 42 Abs. 2 und <ref-law>; vgl. Erwägung 2) ist daher auf die Beschwerde einzutreten.
2.
2.1. Mit Beschwerde in Zivilsachen können Rechtsverletzungen nach Art. 95 und 96 BGG gerügt werden. Die Beschwerde ist hinreichend zu begründen, andernfalls wird darauf nicht eingetreten (<ref-ruling> E. 2.1). In der Beschwerdeschrift ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (<ref-law>). Unerlässlich ist, dass die Beschwerde auf die Begründung des angefochtenen Entscheids eingeht und im Einzelnen aufzeigt, worin eine Verletzung von Bundesrecht liegt. Die beschwerdeführende Partei soll in der Beschwerdeschrift nicht bloss die Rechtsstandpunkte, die sie im kantonalen Verfahren eingenommen hat, erneut bekräftigen, sondern mit ihrer Kritik an den als rechtsfehlerhaft erachteten Erwägungen der Vorinstanz ansetzen (<ref-ruling> E. 2 S. 89, 115 E. 2 S. 116).
Die Beschwerde ist innert der Beschwerdefrist vollständig begründet einzureichen (vgl. <ref-law>). Vor Bundesgericht findet in der Regel nur ein Schriftenwechsel statt (<ref-law>). Kommt es zu einem zweiten Schriftenwechsel, darf die beschwerdeführende Partei die Replik nicht dazu verwenden, ihre Beschwerde zu ergänzen oder zu verbessern (<ref-ruling> E. 1.7; <ref-ruling> E. 3.3.4). Mit Rügen, welche die beschwerdeführende Partei bereits in der Beschwerde hätte erheben können, ist sie nach Ablauf der Beschwerdefrist ausgeschlossen (<ref-ruling> E. 2.2; <ref-ruling> E. 1.7; <ref-ruling> E. 3.3.4 mit Hinweisen). Die Replik ist nur zu Darlegungen zu verwenden, zu denen die Ausführungen in der Vernehmlassung eines anderen Verfahrensbeteiligten Anlass geben (vgl. <ref-ruling> E. 2.2). Soweit die Beschwerdeführer in ihrer Replik darüber hinausgehen, können sie nicht gehört werden.
2.2. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Dazu gehören sowohl die Feststellungen über den streitgegenständlichen Lebenssachverhalt als auch jene über den Ablauf des vor- und erstinstanzlichen Verfahrens, also die Feststellungen über den Prozesssachverhalt (<ref-ruling> E. 1.3.1 mit Hinweisen). Es kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 2 S. 117; <ref-ruling> E. 1.5). Überdies muss die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein können (<ref-law>).
Für eine Kritik am festgestellten Sachverhalt gilt das strenge Rügeprinzip von <ref-law> (<ref-ruling> E. 2.3 S. 266 mit Hinweisen). Die Partei, welche die Sachverhaltsfeststellung der Vorinstanz anfechten will, muss klar und substanziiert aufzeigen, inwiefern diese Voraussetzungen erfüllt sein sollen (<ref-ruling> E. 1.3.1 S. 18 mit Hinweisen). Wenn sie den Sachverhalt ergänzen will, hat sie zudem mit präzisen Aktenhinweisen darzulegen, dass sie entsprechende rechtsrelevante Tatsachen und taugliche Beweismittel bereits bei den Vorinstanzen prozesskonform eingebracht hat (<ref-ruling> E. 2 S. 90). Genügt die Kritik diesen Anforderungen nicht, können Vorbringen mit Bezug auf einen Sachverhalt, der vom angefochtenen Entscheid abweicht, nicht berücksichtigt werden (<ref-ruling> E. 1.3.1 S. 18).
2.3.
2.3.1. Diese Grundsätze verkennen die Beschwerdeführer, soweit sie unter dem Titel "Zum Sachverhalt" den Sachverhalt aus ihrer eigenen Sicht schildern und über den vorinstanzlich festgestellten Sachverhalt hinausgehen, ohne Sachverhaltsrügen nach den obigen Grundsätzen zu erheben. Diese Ausführungen haben unbeachtet zu bleiben.
Die Beschwerdeführer berufen sich darauf, sie hätten im Schreiben vom 5. Oktober 2016 erwähnt, dass sie als Architekten vom Fach seien und sie sich auf "verschiedene Szenarien" einstellen könnten. Sie gehen damit über den vorinstanzlich festgestellten Sachverhalt hinaus, ohne eine hinreichende Sachverhaltsrüge zu erheben. Auch dies kann im Folgenden nicht berücksichtigt werden.
2.3.2. Zu ihrem Eventualantrag auf Rückweisung der Sache an die Vorinstanz (Rechtsbegehren Ziff. 4) erklären die Beschwerdeführer lediglich pauschal das Folgende: Sollte das Bundesgericht zur Ansicht gelangen, dass die Vorinstanz den rechtserheblichen Sachverhalt "in Beachtung der sozialen Untersuchungsmaxime" unvollständig festgestellt habe, sei die Sache an die Vorinstanz zurückzuweisen. Damit genügen sie den oben genannten Rügeanforderungen offensichtlich nicht, sodass darauf von vornherein nicht einzutreten ist.
2.3.3. Auch auf den Antrag um Erstreckung der Mietverhältnisse über die Mansarden (Rechtsbegehren Ziff. 3) kann nicht eingetreten werden: Die Erstinstanz erklärte die Kündigungen der Mietverhältnisse über die 4-Zimmerwohnung und über die Mansardenzimmer für gültig und prüfte von Amtes wegen eine Erstreckung der Mietverhältnisse. Im Berufungsverfahren vor der Vorinstanz akzeptierten die Beschwerdeführer ausdrücklich die Kündigung der Mansardenzimmer, begehrten aber eine Erstreckung. Die Vorinstanz erwog zur Erstreckung der Mietverhältnisse über die Mansarden, die Beschwerdeführer würden in ihrer Berufung nichts dazu ausführen und auch nicht auf ihre erstinstanzliche Argumentation verweisen. Mangels ausreichender Begründung sei daher auf das entsprechende Rechtsbegehren nicht einzutreten.
Vor Bundesgericht wäre es an den Beschwerdeführern aufzuzeigen, dass sie entgegen der Vorinstanz ihren Begründungspflichten an die kantonale Berufungsschrift nachgekommen wären oder die Vorinstanz die Anforderungen an die Begründung bundesrechtswidrig überspannt hätte. Dies rügen die Beschwerdeführer nicht. Sie legen vielmehr dar, dass ein Grund für eine Erstreckung der Miete für die beiden Mansardenzimmer vorliege. Darauf ist nicht einzutreten, fehlt es doch diesbezüglich an der materiellen Ausschöpfung des Instanzenzuges (vgl. <ref-ruling> E. 1.1 S. 293). Selbst wenn von einem zulässigen Vorbringen ausgegangen würde, fehlte es bezüglich der Erstreckung an Sachverhaltsfeststellungen der Vorinstanz, die der Argumentation der Beschwerdeführer zugrunde gelegt werden könnten (vgl. Erwägung 2.2), da sich die Vorinstanz nicht zur allfälligen Härte bzw. Interessenlage der Parteien bei der Erstreckung äusserte.
3.
Vor Bundesgericht ist damit einzig die Gültigkeit der Kündigung des Mietverhältnisses über die 4-Zimmerwohnung zu prüfen.
Die Vorinstanz erwog, den Beschwerdeführern gelänge es nicht, zu beweisen oder darzutun, dass die Kündigung mangels Sanierungsabsicht missbräuchlich sei. Ebensowenig sei die Kündigung deshalb missbräuchlich, weil die Beschwerdeführer der Beschwerdegegnerin am 5. Oktober 2016 geschrieben hätten, während den Sanierungsarbeiten anderswo zu wohnen. Der Erstinstanz sei beizupflichten, dass es sich bei diesem Schreiben um eine blosse Erklärung handle, ohne weitere Präzisierungen zu Wohnmöglichkeiten oder anderweitigen Garantien. Auch der Umstand, dass die Beschwerdeführer nach erfolgter Kündigung eine andere Wohnung gemietet hätten, habe unberücksichtigt zu bleiben. Schliesslich könnten die Beschwerdeführer die Missbräuchlichkeit der Kündigung auch nicht aus dem Antwortschreiben der Beschwerdegegnerin vom 10. Oktober 2016 oder aus dem nachfolgenden Verhalten der Beschwerdegegnerin ableiten. Die Beschwerdeführer hätten die Treuwidrigkeit der Kündigung nicht nachgewiesen.
4.
4.1.
4.1.1. Dagegen beharren die Beschwerdeführer auf ihrer Auffassung, die Kündigung sei missbräuchlich, weil sie der Beschwerdegegnerin in ihrem Schreiben vom 5. Oktober 2016 zugesichert hätten, während den Sanierungsarbeiten anderswo zu wohnen. Entgegen der Ansicht der Vorinstanz erschliesse sich aus den Erklärungen der Parteien ohne Weiteres, dass die Beschwerdeführer ihr Angebot ernst gemeint hätten und dass sie von der Beschwerdegegnerin auch ernst genommen worden seien. Anders lasse sich die Reaktion der Beschwerdegegnerin im Schreiben vom 10. Oktober 2016 nicht erklären. Es treffe zwar zu, dass die Beschwerdeführer im Schreiben vom 5. Oktober 2016 nicht konkretisiert hätten, wo sie während der Sanierungsarbeiten wohnen würden. Es sei aber nicht ersichtlich, inwiefern sie im damaligen Zeitpunkt in der Lage gewesen sein sollten, ihr Angebot noch mehr zu konkretisieren als sie es taten. Es könne daher nicht gesagt werden, das Angebot der Beschwerdeführer mit Schreiben vom 5. Oktober 2016 sei zu wenig konkret, um als ernsthaft im Sinne der bundesgerichtlichen Rechtsprechung zu gelten.
4.1.2. Die ordentliche Kündigung eines Mietvertrags setzt keine besonderen Kündigungsgründe voraus. Mieter und Vermieter sind grundsätzlich frei, das (unbefristete) Mietverhältnis unter Einhaltung der Fristen und Termine zu kündigen (<ref-law>). Einzige Schranke bildet der Grundsatz von Treu und Glauben: Bei der Miete von Wohn- und Geschäftsräumen ist die Kündigung anfechtbar, wenn sie gegen diesen Grundsatz verstösst (<ref-law>; vgl. auch <ref-law>). Allgemein gilt eine Kündigung als treuwidrig, wenn sie ohne objektives, ernsthaftes und schützenswertes Interesse und damit aus reiner Schikane erfolgt oder Interessen der Parteien tangiert, die in einem krassen Missverhältnis zueinander stehen. Der Umstand, dass die Kündigung für den Mieter eine Härte darstellt, genügt nicht; eine solche ist nur im Hinblick auf eine Erstreckung des Mietverhältnisses nach <ref-law> relevant (<ref-ruling> E. 3.2.1 S. 92 f.; <ref-ruling> E. 4.1 S. 497; <ref-ruling> E. 2.1 S. 62; je mit Hinweisen).
Ob eine Kündigung gegen Treu und Glauben verstösst, beurteilt sich in Bezug auf den Zeitpunkt, in dem sie ausgesprochen wird (<ref-ruling> E. 3.2.1 S. 92 f.; <ref-ruling> E. 4.1 S. 497; <ref-ruling> E. 2.1 S. 62). Umstände, die sich erst nach diesem Zeitpunkt ereignen, können eine ursprünglich zulässige Kündigung nicht im Nachhinein zu einer missbräuchlichen machen, sondern erlauben höchstens Rückschlüsse auf die Situation im Kündigungszeitpunkt (Urteile 4A_127/2017 vom 25. Oktober 2017 E. 3.2; 4A_142/2017 vom 3. August 2017 E. 4.1).
4.1.3. Die Beschwerdeführer teilten nach den Feststellungen der Vorinstanz der Beschwerdegegnerin mit Schreiben vom 5. Oktober 2016 mit, um eine Leerkündigung zu vermeiden könne sich die Mieterschaft vorstellen, während der Umbauphase eine andere Wohnung zu beziehen oder innerhalb der Liegenschaft zu rotieren. Sie selbst seien bereit, ihre Wohnung zeitweilig zu räumen.
Die Beschwerdeführer brachten damit lediglich die vage Möglichkeit zum Ausdruck, dass sie sich einen Auszug aus der Mietwohnung während der Umbauphase vorstellen könnten. Es handelt sich dabei klarerweise nicht um ein ernsthaftes und bedingungsloses Angebot, während der Umbau- oder Sanierungsarbeiten anderswo zu wohnen, das die Kündigung des Mietverhältnisses im Einzelfall treuwidrig erscheinen lassen könnte, wie dies vereinzelt erwogen wurde (vgl. Urteile 4A_127/2017 vom 25. Oktober 2017 E. 3.2; 4A_503/2013 vom 5. März 2014 E. 4.2; 4A_126/2012 vom 3. August 2012 E. 4.2). Daran ändert nichts, dass die Beschwerdeführer im September 2017 und damit sechs Monate nach erfolgter Kündigung in der Nähe der gekündigten Wohnung eine "Ausweichwohnung" mieteten. Ebensowenig lässt sich ein ernsthaftes Angebot der Beschwerdeführer aus dem Antwortschreiben der Beschwerdegegnerin vom 10. Oktober 2016 herleiten.
4.2.
4.2.1. Die Beschwerdeführer berufen sich darauf, die Beschwerdegegnerin habe im Schreiben vom 10. Oktober 2016 ausgeführt, sie werde die Beschwerdeführer regelmässig über das Bauvorhaben informieren. Im Kontext mit dem Schreiben der Beschwerdeführer vom 5. Oktober 2016 könne der Inhalt des Schreibens vom 10. Oktober 2016 nicht anders verstanden werden, als dass die Beschwerdegegnerin die Beschwerdeführer wieder informieren werde, sobald sie über die Grundlagen verfüge, auf das Angebot der Beschwerdeführer einzugehen. Die Beschwerdegegnerin habe damit ein berechtigtes Vertrauen gesetzt, vorgängig über den Zeitpunkt des Baubeginns sowie die Dauer und Ausgestaltung des Bauvorhabens zu informieren. Die Beschwerdeführer hätten nicht damit rechnen müssen, dass die Beschwerdegegnerin die Mietverhältnisse kündigen würde, bevor diese mit den in Aussicht gestellten Informationen über das Bauvorhaben wieder auf sie zukommen würde. Das Verhalten der Beschwerdegegnerin erweise sich daher als treuwidrig.
4.2.2. Nach den unbestrittenen Feststellungen der Vorinstanz erklärte die Beschwerdegegnerin im Schreiben vom 10. Oktober 2016 gegenüber den Beschwerdeführern, eine abschliessende Beurteilung der von den Beschwerdeführern unterbreiteten Vorschläge sei noch nicht möglich. Sie würden aber die Mieter, wie sie dies an der Mieterorientierung kommuniziert habe, über das Bauvorhaben regelmässig informieren.
Die Beschwerdegegnerin erklärte in diesem Schreiben also nur, dass sie die von den Beschwerdeführern gemachten Vorschläge im damaligen Zeitpunkt noch nicht abschliessend beurteilen könne. Entgegen der Auffassung der Beschwerdeführer sicherte die Beschwerdegegnerin in diesem Antwortschreiben aber nicht zu, dass sie vor dem Aussprechen der Kündigung des Mietvertrages noch einmal mit den Beschwerdeführern Kontakt aufnehmen würde, um auf den Vorschlag der Beschwerdeführer einzugehen, die Wohnung während der Sanierung einstweilig zu verlassen.
Die Vorinstanz stellte fest, die Beschwerdeführer hätten seit der Mieterorientierung vom 27. September 2016 Kenntnis von der Kündigungsabsicht der Beschwerdegegnerin. Aus dem Schreiben der Beschwerdegegnerin vom 10. Oktober 2016 geht nicht hervor, dass die Beschwerdegegnerin die Kündigung überdenken werde, noch dass sie die Beschwerdeführer vor dem Aussprechen der Kündigung nochmals informieren würde. Die Beschwerdegegnerin erklärte einzig, dass sie über das Bauvorhaben regelmässig informieren würde. Einzig der Umstand, dass die Beschwerdegegnerin die Beschwerdeführer entgegen deren Erwartungen nicht regelmässig über das Bauvorhaben informierte, macht aber unter den vorliegenden Umständen die Kündigung nicht treuwidrig.
4.3. Nach dem Gesagten vermögen die Beschwerdeführer nicht aufzuzeigen, dass die Vorinstanz Bundesrecht verletzt hätte, als sie zum Schluss kam, dass die Kündigung vom 28. Februar 2017 nicht missbräuchlich ist.
5.
Die Beschwerdeführer verlangen in Rechtsbegehren Ziff. 5 eine andere Verteilung der vorinstanzlichen Kosten- und Entschädigungsfolgen. Da eine Begründung dieses Antrages fehlt, ist nach Treu und Glauben davon auszugehen, dass die Beschwerdeführer damit eine andere Verteilung der vorinstanzlichen Kosten- und Entschädigungsfolgen für den Fall der Gutheissung ihrer Beschwerde begehren. Da die Beschwerde nach dem Ausgeführten nicht gutgeheissen werden kann, erübrigt sich auch eine andere Verteilung der Kosten- und Entschädigungsfolgen des vorinstanzlichen Verfahrens.
6.
Das Gesuch um aufschiebende Wirkung wird mit dem Entscheid in der Sache gegenstandslos.
7.
Nach dem Ausgeführten ist die Beschwerde abzuweisen, soweit auf sie überhaupt eingetreten werden kann. Dem Ausgang des Verfahrens entsprechend werden die Beschwerdeführer unter solidarischer Haftbarkeit kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und 5, Art. 68 Abs. 1 und 4 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 3'000.-- werden den Beschwerdeführern in solidarischer Haftbarkeit auferlegt.
3.
Die Beschwerdeführer haben unter solidarischer Haftbarkeit die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 3'500.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 5. Februar 2019
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Kiss
Der Gerichtsschreiber: Brugger