Sachverhalt: A. A.a. Am 30. September 2008 wurde C._ (Verkäuferin, Beklagte, Widerklägerin) die Baubewilligung für drei Mehrfamilienhäuser mit Flachdach an der Strasse Q._ in R._ erteilt. Die Wohnungen im Haus Nr. sss wurden im Stockwerkeigentum erstellt und einzeln verkauft. A.b. Am 14. Mai 2010 kauften A._ und B._ (Käufer, Kläger, Widerbeklagte) mit öffentlich beurkundetem Vertrag die Attikawohnung Nr. ttt im obersten Geschoss des Hauses Nr. sss zu einem pauschalen Kaufpreis von Fr. 2'500'000.--. Dazu kamen Mehrkosten für individuelle Sonderausbauwünsche der Käufer, die separat abzurechnen waren. Grundlage des Kaufvertrags waren die folgenden Dokumente: Entwürfe vom 1. Dezember 2009 zur Begründung von Stockwerkeigentum mit Aufteilungsplänen und zum Stockwerkeigentümerreglement, detaillierter Bau- und Raumbeschrieb vom 30. November 2009, Baubewilligung und Vereinbarung für die Ausführung der Käuferwünsche. Für den Fall eines Widerspruchs zwischen diesen Dokumenten sollte der detaillierte Bau- und Raumbeschrieb massgeblich sein. A.c. Die Käufer interessierten sich für eine Nutzung des Dachs als Dachterrasse, was für sie mindestens den Bau eines bequemen Dachzugangs voraussetzte. Die Käufer wünschten eine räumliche Verlegung des zunächst als Verlängerung des Treppenhauses geplanten, einfachen Dachausstiegs zu Unterhaltszwecken ins Zentrum der Wohnung, eine architektonisch ansprechende Gestaltung dieser Treppe und einen bequemen Dachdurchstieg mittels elektronisch zu öffnender Drehtür. Der gewünschte Zugang auf das Dach wurde im Verlauf der Bauarbeiten realisiert. A.d. Der Bezug der Wohnung war geplant für den 1. Oktober 2011. Anlässlich einer baupolizeilichen Inspektion des Hauses wurden u.a. der ohne Baubewilligung gebaute Dachzugang samt Treppe im Wohnzimmer der Wohnung der Käufer sowie gewisse Ausbauten auf dem Dach festgestellt. Am 18. August 2011 wurde daher ein Baustopp erlassen. Nach Zusicherung eines festen Verschlusses des Dachaufstiegs und des Abbruchs der Zugangstreppe im Wohnzimmer bis zum Vorliegen der nötigen Baubewilligung wurde der Baustopp am 13. September 2011 wieder aufgehoben. Nach Vornahme dieser Arbeiten wurde am 5. Oktober 2011 die behördliche Bezugsbewilligung per 30. September 2011 erteilt. A.e. Am 13. Oktober 2011 forderte die Verkäuferin die Käufer zur Mitwirkung an der Eigentumsübertragung auf. Da die Käufer zwischenzeitlich vom zuständigen Bausekretär der Gemeinde erfahren hatten, dass dieser die Nutzung des Dachs als Dachterrasse nie als bewilligungsfähig erachtet hatte, setzten die Käufer der Verkäuferin am 13. Oktober 2011 eine Nachfrist bis zum 28. Oktober 2011 an, um den vereinbarten Zugang zum Dach zu erstellen; dieser sei für sie eine wesentliche Vertragsgrundlage gewesen. A.f. Am 31. Oktober 2011 erklärten die Käufer den Rücktritt vom Vertrag und verweigerten den Eigentumsantritt. A.g. Um die beantragte nachträgliche Baubewilligung für die Nutzung des Dachs als Terrasse und für den Bau einer Absturzsicherung zu erhalten, gelangte die Verkäuferin bis ans Verwaltungsgericht; die Baubewilligung wurde schliesslich am 13. Mai 2014 erteilt. B. B.a. Nachdem im Schlichtungsverfahren die Klagebewilligung ausgestellt worden war, reichten die Käufer am 8. Juni 2012 beim Bezirksgericht Meilen Klage ein. Sie beantragten, die Verkäuferin sei zur Zahlung von Fr. 620'000.-- (Anzahlung Kaufpreis Fr. 500'000.--, Vorauszahlung Käuferausbauwünsche Fr. 120'000.--) nebst Zins sowie von Fr. 34'523.05 (Schadenersatz für Umtriebe) nebst Zins zu verpflichten. Die Verkäuferin erhob Widerklage mit folgenden Anträgen: "1. Es seien die Kläger zu verpflichten, das Eigentum an den Liegenschaften R._ Grundbuch Blatt uuu (Wohnung Nr. ttt), Grundbuch Blatt vvv (Bastelraum Nr. www) und Grundbuch Blatt xxx (Garagenplätze Nr. _ und _) zu übernehmen und Zug um Zug gegen Abgabe der entsprechenden Grundbuchanmeldung auf Eigentumsübertragung durch die Beklagte folgende restlichen Kaufpreiszahlungen an die Beklagte zu leisten, nämlich: a) Fr. 125'000.-- zuzüglich 5 % Zins seit 1. November 2011 auf das Konto Nr. yyy der Politischen Gemeinde R._ bei der Bank E._, sowie b) Fr. 1'875'000.-- zuzüglich 5 % Zins seit 1. November 2011 auf das Konto IBAN Nr. zzz der Beklagten bei der Bank D._. 2. Im Weiteren seien die Kläger zu verpflichten, der Beklagten für die durch die Bestellungsänderungen bewirkten Mehrkosten einen Betrag von Fr. 182'423.-- zuzüglich 5 % Zins seit 1. November 2011 zu bezahlen, Zug um Zug gegen Abgabe der entsprechenden Grundbuchanmeldung auf Eigentumsübertragung durch die Beklagte. 3. (Kosten- und Entschädigungsfolgen) " Die Verkäuferin stellte im Rahmen ihrer Widerklage zudem das Eventualbegehren, den Käufern sei eine Preisminderung oder Entschädigung nach richterlichem Ermessen, maximal aber Fr. 50'000.-- zuzusprechen. B.b. Mit Urteil vom 22. Juni 2015 verpflichtete das Bezirksgericht Meilen die Verkäuferin, den Käufern Fr. 620'000.-- nebst Zins zu bezahlen. Im Mehrumfang wies das Bezirksgericht die Hauptklage ab. Die Widerklage wies es ebenfalls ab. Das Bezirksgericht kam zum Schluss, nach einer objektiven Auslegung des zwischen den Parteien geschlossenen Vertrags habe die Verkäuferin die Erstellung einer Dachterrasse mit entsprechender Treppe geschuldet. Die Käufer seien daher gültig vom Vertrag zurückgetreten. B.c. Gegen dieses Urteil erhob die Verkäuferin Berufung an das Obergericht des Kantons Zürich. Sie beantragte die Aufhebung des erstinstanzlichen Urteils und wiederholte im Wesentlichen die vor dem Bezirksgericht gestellten Anträge. B.d. Am 19. Februar 2016 erliess das Obergericht des Kantons Zürich ein Teil-Urteil und mehrere Beschlüsse: Beschluss 1: "1. Es wird festgestellt, dass Dispositiv Ziffer 1 Abs. 2 des Urteils des Bezirksgerichts Meilen vom 22. Juni 2015, womit die Hauptklage im Fr. 620'000.-- zuzüglich Zins zu 5 % seit 1. Januar 2012 übersteigenden Betrag abgewiesen wurde, am 5. November 2015 in Rechtskraft erwachsen ist." 2. (Mitteilung und Rechtsmittelbelehrung) " Teil-Urteil: "1. Das Urteil des Bezirksgerichts Meilen vom 22. Juni 2015 wird aufgehoben und die Hauptklage auch im übrigen Umfang abgewiesen. 2. In Gutheissung des Widerklagebegehrens Ziffer 1 werden die Kläger verpflichtet, das Eigentum an den Liegenschaften R._ Grundbuch Blatt uuu (Wohnung Nr. ttt), Grundbuch Blatt vvv (Bastelraum Nr. www) und Grundbuch Blatt xxx (Garagenplätze Nr. _ und _) zu übernehmen und Zug um Zug gegen Abgabe der entsprechenden Grundbuchanmeldung auf Eigentumsübertragung durch die Beklagte folgende restlichen Kaufpreiszahlungen an die Beklagte zu leisten, nämlich: a) Fr. 125'000.-- zuzüglich 5 % Zins seit 1. November 2011 auf das Konto Nr. yyy der Politischen Gemeinde R._ bei der Bank E._, sowie b) Fr. 1'875'000.-- zuzüglich 5 % Zins sei 1. November 2011 auf das Konto IBAN Nr. zzz der Beklagten bei der Bank D._. 3.-5. (Entscheidgebühr, Mitteilung, Rechtsmittelbelehrung) " Beschluss 2: "1. Mit Bezug auf das Widerklagebegehren Ziffer 2 wird die Sache zur Ergänzung des Verfahrens und zu neuer Entscheidung im Sinne der Erwägungen an die Vorinstanz zurückgewiesen. 2.-5. (Gerichts- und Parteikosten, Mitteilung, Rechtsmittelbelehrung) " Das Obergericht kam zum Schluss, die Rüge der falschen Vertragsauslegung sei begründet. Entgegen der Ansicht des Bezirksgerichts seien die baulichen Arbeiten für einen Komfortausstieg aus dem Wohnzimmer bei Beurkundung des Vertrags nicht Gegenstand der vertraglichen Leistungspflichten gewesen. Die Verkäuferin habe sich in einem blossen Teilverzug befunden, weshalb die Käufer nicht zum Rücktritt ex tunc vom beurkundeten Vertrag berechtigt gewesen seien. C. Mit Beschwerde in Zivilsachen vom 12. April 2016 beantragen die Käufer dem Bundesgericht, das Teil-Urteil des Obergerichts des Kantons Zürich sowie dessen Beschluss zum Widerklagebegehren Ziff. 2 seien aufzuheben; eventualiter sei die Sache an die Vorinstanz zu neuem Entscheid zurückzuweisen. Die Beschwerdeführer beantragen zudem, der Beschwerde sei die aufschiebende Wirkung zu erteilen. Die Beschwerdegegnerin beantragt, auf die Beschwerde sei nicht einzutreten; eventualiter sei die Beschwerde abzuweisen. Die Vorinstanz hat auf Vernehmlassung verzichtet. Die Parteien haben Replik und Duplik eingereicht. D. Mit Präsidialverfügung vom 30. Mai 2016 wurde der Beschwerde die aufschiebende Wirkung erteilt.