Sachverhalt: A. A.a. Die X._ AG (Bestellerin, Beklagte, Beschwerdeführerin) plante ab 2009 ein neues Zentrallager an ihrem Sitz in A._, Österreich. Im Hinblick darauf schloss sie mit der Y._ GmbH (Unternehmerin, Klägerin, Beschwerdegegnerin; Sitz in B._, Deutschland) Werkverträge ab. Darin verpflichtete sich die Unternehmerin zur Herstellung und Montage von Regalanlagen nach den Vorgaben der Bestellerin. A.b. Mit E-Mail vom 14. Oktober 2010 stellte die Unternehmerin der Bestellerin zwei Werkverträge zu, einen betreffend das Schnittholz- und Plattenlager sowie einen betreffend das Automatiklager. Auf den beiden letzten Seiten der Vertragsurkunden wurde auf die Verkaufs-, Liefer- und Zahlungsbedingungen sowie Montagebedingungen bei Montageausführung der Unternehmerin verwiesen sowie darauf, dass diese unter einer bestimmten Faxnummer angefordert werden könnten. In § 15.6 der Verkaufs-, Liefer- und Zahlungsbedingungen befindet sich eine Gerichtsstandsklausel mit folgendem Wortlaut: "Sämtliche Streitigkeiten aus oder im Zusammenhang mit dieser Vertragsbeziehung (inklusive Streitigkeiten betreffend Gültigkeit und Auflösung dieses Vertrages und der Gültigkeit der Gerichtsstandsklausel) sind ausschliesslich durch die für die Stadt Zürich zuständigen Gerichte zu entscheiden; (...) Soweit gesetzlich zulässig sind vorgenannte Auseinandersetzungen in sachlicher Hinsicht ausschliesslich vom Handelsgericht des Kantons Zürich zu beurteilen. (...) " Die Bestellerin unterzeichnete je das letzte Blatt der Vertragsurkunden und retournierte diese an die Unternehmerin. A.c. Anlässlich einer späteren Änderung betreffend das Plattenlager wies die Unternehmerin darauf hin, dass ihre Bedingungen im Internet heruntergeladen werden könnten. B. Am 26. Juni 2012 reichte die Unternehmerin beim Handelsgericht des Kantons Zürich Klage ein und beantragte, die Bestellerin sei zur Zahlung von EUR 667'603.30 nebst Zins zu verurteilen. Es handelt sich dabei um angeblich ausstehende Beträge für ausgeführte Arbeiten. Mit Eingabe vom 22. Oktober 2012 erhob die Bestellerin die Einrede der Unzuständigkeit. Mit Beschluss vom 11. Januar 2013 wies das Handelsgericht des Kantons Zürich die Unzuständigkeitseinrede der Bestellerin ab. C. Mit Beschwerde in Zivilsachen vom 14. Februar 2013 beantragt die Bestellerin dem Bundesgericht, es sei der Beschluss des Handelsgerichts aufzuheben und die Unzuständigkeit des Handelsgerichts Zürich festzustellen. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde, eventualiter die Rückweisung der Sache an die Vorinstanz zur Beurteilung der Frage, ob eine gerichtsstandsbegründende Erfüllungsortsvereinbarung vorliege. Die Vorinstanz hat auf Vernehmlassung verzichtet. Die Parteien haben unaufgefordert Replik und Duplik eingereicht.