Sachverhalt: A. A. und B. X._ (Kläger, Beschwerdeführer) waren über viele Jahre Bankkunden bei der Bank Y._ (Beklagte, Beschwerdegegnerin), bei der sie ein Schrankfach (Safe) gemietet und ein Kontokorrent-Konto eröffnet hatten. Im Jahre 2006 beabsichtigten A. und B. X._, bei der Bank Y._ auch ein Nummernkonto zu errichten, wozu ihnen D._ behilflich sein sollte. D._ seinerseits kannte C._ (Nebenintervenient), der im Private Banking der Bank Y._ als Kundenberater arbeitete. In der Folge wurden A. und B. X._ - im Beisein von D._ - mindestens zweimal von C._ an seinem Arbeitsplatz, in den Räumlichkeiten der Bank Y._, empfangen. C._ erklärte A. und B. X._, dass für die Errichtung eines Nummernkontos ein Mindestbetrag von Fr. 1 Mio. erforderlich sei, aber bis zum Erreichen des Mindestbetrags eine Zwischenlösung gefunden werden könne. C._ verfasste in den Räumlichkeiten der Bank Y._ die Vereinbarungen vom 28. April 2006 und vom 2. Juni 2006. In diesen zwischen A. und B. X._ einerseits und D._ andererseits abgeschlossenen Vereinbarungen wurde festgehalten, dass das Geld zunächst D._ anvertraut und bei Erreichen des Mindestbetrags sodann auf das gewünschte Nummernkonto einbezahlt werde. In der Folge überreichten A. und B. X._ D._ gesamthaft Fr. 870'000.-- in bar, die er anderweitig verwendete. D._ wurde später für sein Verhalten zum Nachteil von A. und B. X._ wegen Betrugs, C._ wegen Gehilfenschaft zu Betrug verurteilt. B. B.a. Am 10. März 2010 reichten A. und B. X._ beim Handelsgericht des Kantons Zürich Klage ein mit dem Rechtsbegehren, es sei die Bank Y._ zur Zahlung von Fr. 870'000.-- zuzüglich Zins zu verpflichten. Im Laufe des Verfahrens änderten die Kläger ihr Begehren und setzten ihr Zahlungsbegehren auf Fr. 580'000.-- herab, zuzüglich Zins zu 5 % auf verschiedene Beträge ab unterschiedlichen Zeitpunkten; zudem sei die Beklagte zu verpflichten, ihnen die Kosten für das Friedensrichterverfahren in der Höhe von Fr. 1'060.-- zu ersetzen. Mit Urteil vom 22. Juni 2012 schrieb das Handelsgericht des Kantons Zürich das Verfahren im Umfang von Fr. 290'000.-- als gegenstandslos ab und hiess die Klage im Umfang von Fr. 435'000.-- nebst Zins zu 5 % seit dem 28. April 2006 gut. B.b. Mit Urteil vom 22. Januar 2013 hiess das Bundesgericht eine von der Beklagten gegen das handelsgerichtliche Urteil vom 22. Juni 2012 erhobene Beschwerde teilweise gut, es hob das angefochtene Urteil auf und wies die Sache zu neuer Entscheidung an die Vorinstanz zurück. B.c. Nach erfolgter Rückweisung verpflichtete das Handelsgericht die Beklagte mit Urteil vom 23. Mai 2013 zur Zahlung von Fr. 145'000.-- nebst Zins zu 5 % seit dem 1. April 2011 sowie Zins zu 5 % auf Fr. 400'000.-- vom 28. April 2006 bis 19. Juli 2006, auf Fr. 435'000.-- vom 19. Juli 2006 bis 3. Februar 2011, auf Fr. 185'000.-- vom 3. Februar 2011 bis 2. März 2011 und auf Fr. 175'000.-- vom 2. März 2011 bis 1. April 2011; im Mehrbetrag wies es die Klage ab (Dispositiv-Ziffer 1). Die Vorinstanz bestätigte zunächst ihre Erwägung, dass der eingetretene Schaden von Fr. 870'000.-- grundsätzlich von der Beklagten zu ersetzen, der zu leistende Schadenersatz jedoch angesichts des Selbstverschuldens der Kläger um die Hälfte herabzusetzen und der von der Beklagten zu leistende Betrag entsprechend grundsätzlich auf Fr. 435'000.-- zu bemessen sei. Sie hielt zudem fest, nach Angaben der Kläger seien während des hängigen Verfahrens insgesamt Fr. 290'000.-- auf Rechnung der klägerischen Forderung bezahlt worden. Die Kläger hätten sich während des Behauptungsverfahrens nicht dazu geäussert, wer diese Zahlung geleistet habe; sie seien jedoch auf ihre im Prozess deponierten Erklärungen zu behaften, wonach dieser Betrag mit "für die Beklagte befreiender Wirkung" bezahlt worden sei. Dies habe so verstanden werden dürfen, dass diese Summe vom gerichtlich bemessenen Schadenersatzanspruch gegenüber der Beklagten abzuziehen sei. Der Schadenersatzanspruch betrage Fr. 435'000.--, weshalb den Klägern nach Abzug des der Beklagten mit befreiender Wirkung geleisteten Betrags von Fr. 290'000.-- noch Fr. 145'000.-- (nebst Zins) zuzusprechen sei. C. Mit Beschwerde in Zivilsachen beantragen die Kläger dem Bundesgericht, es sei Dispositiv-Ziffer 1 des Urteils des Handelsgerichts des Kantons Zürich vom 23. Mai 2013 aufzuheben und es sei die Beklagte zur Zahlung von Fr. 435'000.-- zu verpflichten, zuzüglich Zins zu 5 % auf Fr. 400'000.-- seit dem 28. April 2006 und 5 % auf Fr. 35'000.-- seit dem 19. Juli 2006. Eventualiter sei das angefochtene Urteil aufzuheben und die Sache zu neuer Beurteilung an die Vorinstanz zurückzuweisen. Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Vorinstanz hat auf eine Vernehmlassung verzichtet. 