Sachverhalt: A. A.a. Die Y._ GmbH (Klägerin 2, Beschwerdeführerin 2) pachtete mit Unterpachtvertrag vom 29. April 2006, der bis zum 30. September 2013 fest und unkündbar abgeschlossen wurde, von der Q._ AG die damaligen Räumlichkeiten der Bar R._ im UG, EG und 1. OG an der S._strasse in T._. Mit Vereinbarung vom 3./5. Oktober 2006 wurde der Unterpachtvertrag von der Unterverpächterin Q._ AG auf die Z._ AG (Beklagte, Beschwerdegegnerin) übertragen. Die Klägerin 2 betreibt in den Pachträumlichkeiten die Bar U._. Mit mündlichem Untermietvertrag mieteten die Klägerin 2 und die X._ GmbH (Klägerin 1, Beschwerdeführerin 1) gemeinsam von der damaligen Untervermieterin, der Q._ AG, circa die Hälfte eines (Büro-) Raumes im 3. OG der Liegenschaft S._strasse in T._. In der Folge trat die Beklagte anstelle der Q._ AG in den Mietvertrag ein. A.b. Mit den Klägerinnen je separat zugestellten Schreiben vom 29. August 2011 kündigte die Beklagte auf amtlich bewilligten Formularen das Untermietverhältnis betreffend den Anteil am Büroraum im 3. OG per 31. März 2012 mit der Begründung "Eigenbedarf". B. B.a. Die Klägerinnen fochten die Kündigungen an. Nachdem an der Schlichtungsverhandlung keine Einigung erzielt werden konnte, klagten sie am 2. Dezember 2011 beim Mietgericht Zürich. Sie machten insbesondere geltend, beim Unterpachtvertrag vom 29. April 2006 betreffend die Bar U._ sowie beim mündlichen Nachtrag über das Büro handle es sich um ein einheitliches Mietverhältnis, weshalb das Büro nicht separat gekündigt werden könne. Der Nachtrag sei zwischen den gleichen Parteien geschlossen worden. Das Hinzutreten der Klägerin 1 sei ein blosses buchhalterisches Konstrukt gewesen. Diese Auffassung verwarf das Mietgericht, da die Klägerin 1 sich in einem früheren Verfahren (MB090008) gegen eine von der Beklagten ausgesprochene Kündigung mit der Begründung gewehrt hatte, nicht nur sie, sondern auch die Klägerin 2 sei Mieterin des Büroraums, weshalb die nur an sie gerichtete Kündigung formnichtig sei. Mit Blick auf diese widersprüchlichen Vorbringen wies das Mietgericht die Klage ab und erklärte die Kündigungen vom 29. August 2011 per 31. März 2012 für gültig. Es nahm sodann von der Anerkennung der Beklagten, das Mietverhältnis bis zum 30. Juni 2012 zu erstrecken, Vormerk und wies das Subeventualbegehren (Erstreckung um sechs Jahre) im Übrigen ab. Es auferlegte die Gerichtskosten den Klägerinnen und sprach der Beklagten eine Umtriebsentschädigung von Fr. 2'000.-- zu. B.b. Die Klägerinnen fochten das Urteil des Mietgerichts vom 7. Dezember 2012 mit Berufung beim Obergericht des Kantons Zürich an. Sie beantragten, das Urteil des Mietgerichts sei aufzuheben, die Kündigungen vom 29. August seien für nichtig und eventualiter für ungültig zu erklären; subeventualiter sei das Mietverhältnis um sechs Jahre zu erstrecken. Das Obergericht reduzierte mit Urteil vom 17. April 2013 die vom Mietgericht der Beklagten zugesprochene Umtriebsentschädigung auf Fr. 1'000.--. Im Übrigen wies es die Berufung ab. C. Mit Beschwerde in Zivilsachen beantragen die Klägerinnen dem Bundesgericht, das Urteil des Obergerichts aufzuheben, und sie halten an den vor Obergericht gestellten Anträgen fest. Subsubeventualiter verlangen sie die Rückweisung der Angelegenheit zur Neubeurteilung an das Obergericht. Die Beklagte schliesst auf Abweisung der Beschwerde, während das Obergericht auf eine Stellungnahme verzichtet.