Sachverhalt: A. Mit Mietvertrag vom 27. September 1954 mietete M._, Ehemann von A._ und Vater bzw. Grossvater der Kläger, von der L._ AG (Beklagte, Beschwerdegegnerin) eine 7-Zimmerwohnung in Zürich. Zum Mietobjekt gehörten laut Mietvertrag ein Mansardenzimmer (Mädchenzimmer Nr. 1) und ein Estrichraum (Kofferraum) auf der Winde sowie ein Kellerabteil. Nach dem Tod von M._ ging das Mietverhältnis auf die am 30. August 2012 ebenfalls verstorbene A._ (im Folgenden: die Mieterin) über. Im Jahre 2004 wurden sowohl das Mansardenzimmer als auch der Estrichraum von der Mieterin an die Beklagte zurückgegeben. Das Mietverhältnis wurde am 18. Oktober 2012 per 31. Januar 2013 aufgelöst und bis am 31. Juli 2013 erstreckt. B. Nach einem erfolglosen Schlichtungsversuch beantragten die Kläger (Erben der Mieterin) mit Klage vom 18. März 2013 beim Mietgericht Zürich, die Beklagte sei zu verpflichten, ihnen Fr. 38'595.-- nebst Zins für zu viel bezahlte Mietzinse zu bezahlen. Mit Urteil vom 29. September 2014 wies das Mietgericht die Klage ab. Eine dagegen erhobene Berufung der Kläger wies das Obergericht des Kantons Zürich am 8. April 2015 ab. C. Die Kläger verlangen mit Beschwerde in Zivilsachen, es sei das Urteil des Obergerichts vom 8. April 2015 aufzuheben und die Beklagte zu verpflichten, ihnen Fr. 27'720.-- zu bezahlen zuzüglich Verzugszinsen von 5 % ab 14. November 2012. Die Beklagte beantragt, die Beschwerde sei abzuweisen. Eventualiter sei das Verfahren an die Vorinstanz zurückzuweisen zur Beurteilung ihrer Verrechnungsforderungen. Die Vorinstanz verzichtete auf eine Vernehmlassung zur Beschwerde.