Sachverhalt: A. Die X._ AG (Klägerin und Beschwerdeführerin) ist eine Aktiengesellschaft mit Sitz in der Schweiz. Sie ist weltweit im Luftfahrtgeschäft tätig und erbringt diesbezügliche Dienstleistungen in verschiedenen Bereichen der Luftfahrt. Die Y._ GmbH (Beklagte und Beschwerdegegnerin) ist eine Gesellschaft mit beschränkter Haftung nach deutschem Recht mit Sitz in Frankfurt am Main in Deutschland. Ihr Zweck besteht in der Entwicklung und im Vertrieb von Software und EDV-Systemen sowie in der Beratung und Schulung in diesem Bereich. Die Beklagte sollte der Klägerin eine ERP-Software (Enterprise Resource Planning - Software) liefern. Nach einer Evaluationsphase unterzeichneten die Parteien am 31. Dezember 2010 ein End User Licence Agreement (nachfolgend: EULA) sowie ein Master Services Agreement (nachfolgend: MSA), je mit Ergänzungen und Ausführungsvereinbarungen, insbesondere dem "Supplement to EULA" und dem "Statement of Work" in Ergänzung zum MSA. In der Folge machte die Klägerin geltend, die ERP-Software sei nicht so geliefert und installiert worden, wie von ihr gewünscht. B. Am 27. Juli 2012 reichte die Klägerin beim Handelsgericht des Kantons Zürich Klage ein. In ihrer Klageantwort beantragte die Beklagte primär das Nichteintreten zufolge Unzuständigkeit. Mit Beschluss vom 7. Februar 2013 trat das Handelsgericht auf die Klage nicht ein. Es nahm an, es liege keine gültige Gerichtsstandsvereinbarung im Sinn von Art. 23 Ziff. 1 LugÜ (SR 0.275.12) vor, mit der die Zuständigkeit des Handelsgerichts des Kantons Zürich vereinbart worden wäre. Auch auf Art. 5 Ziff. 1 lit. a LugÜ (Gerichtsstand am Erfüllungsort) lasse sich die Zuständigkeit des Handelsgerichts nicht abstützen. Somit sei die allgemeine Zuständigkeit nach Art. 2 Abs. 1 LugÜ massgeblich, also der Sitz der Beklagten in Deutschland. C. Mit Beschwerde in Zivilsachen beantragt die Klägerin dem Bundesgericht, dieser Beschluss sei aufzuheben, die Unzuständigkeitseinrede sei abzuweisen und die Zuständigkeit des Handelsgerichts des Kantons Zürich sei zu bejahen. Die Sache sei zwecks Eintretens auf die Klage an die Vorinstanz zurückzuweisen, und diese sei anzuweisen, über die vorinstanzlichen Kosten- und Entschädigungsfolgen neu zu befinden. Die Beschwerdegegnerin schliesst auf Abweisung der Beschwerde, soweit darauf eingetreten werden kann, während die Vorinstanz auf Vernehmlassung verzichtet. Die Beschwerdeführerin hat unaufgefordert eine Replik eingereicht. Die Beschwerdegegnerin hat die Ausführungen in der Replik pauschal bestritten und auf Gegenbemerkungen verzichtet. 