Sachverhalt:
A. Am 4. März 2011 machte X._ (Kläger, Beschwerdeführer) beim Bezirksgericht Zürich eine Klage gegen die Y._ AG (Beklagte, Beschwerdegegnerin) anhängig. Am 11. Juli 2011 trat das Bezirksgericht mangels sachlicher Zuständigkeit auf die Klage nicht ein. Dieser Beschluss wurde dem Kläger am 5. August 2011 zugestellt.
B. Mit Eingabe vom 17. Oktober 2011 (Datum Poststempel) machte der Kläger die Klage beim Handelsgericht des Kantons Zürich anhängig. Die Beklagte erhob die Unzuständigkeitseinrede. Mit Statutenänderung vom 30. Juni 2011, im Handelsregister eingetragen am 21. Juli 2011, habe sie ihren Sitz von A._ nach B._ (SZ) verlegt und etwa zeitgleich an der Adresse des ehemaligen Sitzes die "Y._ AG Zweigniederlassung A._" eintragen lassen. Sie war der Meinung, die örtliche Zuständigkeit wäre nur gegeben, wenn für die Rechtshängigkeit das Datum der ersten Eingabe beim Bezirksgericht massgeblich bleibe. <ref-law>, der die Rechtshängigkeit bei fehlender Zuständigkeit und falscher Verfahrensart regelt, finde mit Bezug auf die funktionelle Zuständigkeit keine Anwendung. Diese Auffassung verwarf das Handelsgericht. Es kam allerdings zum Schluss, der Kläger habe die in <ref-law> vorgesehene Monatsfrist zur Einreichung der Klage beim zuständigen Gericht nicht eingehalten. Die Klage gelte daher als beim Handelsgericht neu eingereicht, welchem es aber mit Blick auf den im Kanton Schwyz gelegenen Hauptsitz an der örtlichen Zuständigkeit fehle. Auch eine Zuständigkeit am Ort der Zweigniederlassung (<ref-law>) sei nicht gegeben, da der Kläger seine Forderung auf ein Maklermandat stütze, das am 15. August 2009 erteilt worden sei. In diesem Zeitpunkt habe die Zweigniederlassung noch gar nicht bestanden. Entsprechend sei die gesamte in den Akten befindliche Korrespondenz immer mit der "Y._ AG" und nicht mit der "Y._ AG Zweigniederlassung A._" erfolgt. Dies gelte auch bezüglich des Formulars "Anmeldung für eine Mietliegenschaft" vom 11. November 2009. Aus diesen Gründen schützte das Handelsgericht die Unzuständigkeitseinrede der Beklagten unter Kosten- und Entschädigungsfolgen zu Lasten des Klägers.
C. Mit Beschwerde in Zivilsachen beantragt der Kläger dem Bundesgericht unter Kosten- und Entschädigungsfolgen zu Lasten der Beschwerdegegnerin, den Beschluss des Handelsgerichts aufzuheben und die Sache zur Neubeurteilung an das Handelsgericht zurückzuweisen. Die Beschwerdegegnerin hat sich nicht vernehmen lassen. Das Handelsgericht hat auf Vernehmlassung verzichtet.

Erwägungen:
1. Die Beschwerdeschrift enthält keinen materiellen Antrag, wie er nach <ref-law> erforderlich ist. Der blosse Rückweisungsantrag genügt daher nur, sofern das Bundesgericht, sollte es die Rechtsauffassung des Beschwerdeführers für begründet erachten, kein Sachurteil fällen kann, sondern die Streitsache zur weiteren Abklärung des Sachverhaltes an die Vorinstanz zurückweisen muss (<ref-ruling> E. 3.1 mit Hinweisen). Diese Voraussetzung ist erfüllt, soweit der Beschwerdeführer argumentiert, die Vorinstanz hätte die Unzuständigkeitseinrede verwerfen müssen. Sollte dies zutreffen, wäre die Sache zur materiellen Beurteilung an die Vorinstanz zurückzuweisen.
2. Wird eine Eingabe, die mangels Zuständigkeit zurückgezogen oder auf die nicht eingetreten wurde, innert eines Monates seit dem Rückzug oder dem Nichteintretensentscheid bei der zuständigen Schlichtungsbehörde oder beim zuständigen Gericht neu eingereicht, so gilt als Zeitpunkt der Rechtshängigkeit das Datum der ersten Einreichung. Gleiches gilt, wenn eine Klage nicht im richtigen Verfahren eingereicht wurde (Art. 63 Abs. 1 und 2 ZPO).
2.1 Die Vorinstanz ging davon aus, wenn, wie im zu beurteilenden Fall, gegen einen Nichteintretensentscheid kein Rechtsmittel ergriffen werde, beginne die Monatsfrist zur Einreichung der Eingabe beim zuständigen Gericht nach <ref-law> bereits mit Zustellung des Nichteintretensentscheides. Diese sei am 5. August 2011 erfolgt, so dass die Frist unter Berücksichtigung der Gerichtsferien am 16. August 2011 zu laufen begonnen und am 16. September 2011 geendet habe. Durch die Eingabe vom 17. Oktober 2011 sei sie nicht gewahrt worden.
2.2 Der Beschwerdeführer macht dagegen geltend, <ref-law> spreche nicht von der Eröffnung des Nichteintretensentscheides, weshalb nicht auf diesen Zeitpunkt abgestellt werden dürfe. Fristauslösend sei erst die Rechtskraft des Nichteintretensentscheides, da dem Rechtsuchenden die Rechtsmittelfrist zur Überlegung, ob er das Rechtsmittel ergreifen wolle, gewahrt bleiben müsse.
2.3 Der Gesetzestext ist bezüglich der streitigen Frage nicht eindeutig. Zwar spricht er, wie der Beschwerdeführer hervorhebt, nicht von der Zustellung des Nichteintretensentscheides. Darin unterscheidet er sich von Art. 311 und Art. 321 ZPO, welche für die Einreichung der Berufung und der Beschwerde nach der ZPO ausdrücklich auf die Zustellung des begründeten Entscheides abstellen. Er erwähnt aber auch die Rechtskraft des Nichteintretensentscheides nicht, was naheläge, wenn dem Gesetzgeber die vom Beschwerdeführer bevorzugte Lösung vorgeschwebt hätte. Denkbar ist, dass der Gesetzgeber mit der Formulierung eine unterschiedliche Behandlung ermöglichen wollte, je nachdem, ob gegen den Nichteintretensentscheid ein Rechtsmittel ergriffen wurde (vgl. hierzu das zur Publikation bestimmte Urteil des Bundesgerichts 4A_66/2012 vom 29. Mai 2012 E. 6) oder nicht.
2.4 In der Literatur wird einerseits die Auffassung vertreten, die Monatsfrist nach <ref-law> beginne, wenn kein Rechtsmittel ergriffen wird, mit Rechtskraft des Nichteintretensentscheides (INFANGER, in: Basler Kommentar, Schweizerische Zivilprozessordnung, 2010, N. 15 zu <ref-law>; MÜLLER-CHEN, in: Schweizerische Zivilprozessordnung [ZPO]: Kommentar, Brunner und andere [Hrsg.], 2011, N. 18 f. zu <ref-law>; SCHLEIFFER MARAIS, in: Schweizerische Zivilprozessordnung [ZPO], Baker & McKenzie [Hrsg.], 2010, N. 10 zu <ref-law>; GASSER/RICKLI, Schweizerische Zivilprozessordnung [ZPO]: Kurzkommentar, 2010, N. 5 zu <ref-law>). Es findet sich aber ebenso die Meinung, wenn kein Rechtsmittel ergriffen werde, beginne die Monatsfrist bereits mit der Zustellung beziehungsweise der Eröffnung des Nichteintretensentscheides, nicht erst mit dessen Rechtskraft (SUTTER-SOMM/HEDINGER, in: Kommentar zur Schweizerischen Zivilprozessordnung [ZPO], Sutter-Somm und andere [Hrsg.], 2010, N. 11 zu <ref-law>; PICHONNAZ, in: Commentaire romand, Code des obligations I, 2. Aufl. 2012, N. 10 zu aArt. 139 OR [<ref-law>]; BERTI, in: ZPO: Schweizerische Zivilprozessordnung, Oberhammer [Hrsg.], 2010, N. 12 zu <ref-law>; BOHNET, in: CPC: Code de procédure civile commenté, Bohnet und andere [Hrsg.], 2011, N. 20 zu <ref-law>).
2.5 Der Beschwerdeführer verweist auf eine Lehrmeinung, die davon ausgeht, der Nichteintretensentscheid könnte gar nicht angefochten werden, wenn die Neueinreichung binnen einer Monatsfrist seit dessen Mitteilung erfolgen müsste. Es mangle an der erforderlichen Beschwer, da das Verfahren bei der neu angerufenen Instanz verbindlich seinen Fortgang gefunden habe (INFANGER, a.a.O., N. 15 zu <ref-law>). Diese Auffassung überzeugt nicht:
2.5.1 Zum einen bleibt der Betroffene durch den Nichteintretensentscheid beschwert. Dieser zieht in der Regel (wie im zu beurteilenden Fall) Kosten und Entschädigungsfolgen nach sich. Aber auch davon unabhängig ist eine Partei beschwert, wenn die Klage nicht von dem von ihr angerufenen Gericht behandelt wird. Entsprechend ist die nach <ref-law> mögliche Überweisung einer Streitsache an ein anderes Gericht mit Beschwerde anfechtbar (<ref-law>).
2.5.2 Zum andern fehlt es an der Voraussetzung für die Anwendung von <ref-law>, wenn der Nichteintretensentscheid im Rechtsmittelverfahren aufgehoben wird und das zuerst angerufene Gericht auf die Klage eintritt. Unter diesen Umständen findet das Verfahren bei der neu angerufenen Instanz nicht seinen Fortgang, sondern diese tritt nach Art. 59 Abs. 1 und Abs. 2 lit. d ZPO wegen der prioritären anderweitigen Rechtshängigkeit auf die Klage nicht ein. Dem Beginn der Monatsfrist nach <ref-law> kommt für die Anfechtbarkeit des Nichteintretensentscheides insoweit keine Bedeutung zu.
2.6 <ref-law> verallgemeinert den Grundsatz von aArt. 139 OR, der mit Inkrafttreten der ZPO aufgehoben wurde (Botschaft vom 28. Juni 2006 zur Schweizerischen Zivilprozessordnung [ZPO], BBl 2006 7277 Ziff. 5.4 zu Art. 61 Abs. 1 und 2 E-ZPO). Auch die analogen Regelungen in Art. 34 des Bundesgesetzes über den Gerichtsstand in Zivilsachen (Gerichtsstandsgesetz, GestG) vom 24. März 2000 (AS 2000 2355) sowie aArt. 32 Abs. 3 SchKG, welche gleichzeitig aufgehoben wurden, gehen auf das "Urbild" des aArt. 139 OR zurück (Botschaft vom 18. November 1998 zum Bundesgesetz über den Gerichtsstand in Zivilsachen [Gerichtsstandsgesetz, GestG], BBl 1999 III 2870 Ziff. 26 zu Art. 35 E-GestG). Daher liegt nahe, Lehre und Rechtsprechung zu aArt. 139 OR heranzuziehen.
2.7 In <ref-ruling> erkannte das Bundesgericht in einem Fall, der die analoge Anwendung von aArt. 139 OR auf die Aberkennungsklage mit entsprechend verkürzter Frist (vgl. heute <ref-law>; Botschaft ZPO, BBl 2006 7278 Ziff. 5.4 zu Art. 61 Abs. 3 E-ZPO) betraf, aus Gründen der Rechtssicherheit und der Klarheit der Verhältnisse beginne die Nachfrist erst mit der Zustellung des formellen Nichteintretensentscheides zu laufen (und nicht schon mit der mündlichen Mitteilung). Das Bundesgericht stellte mithin nicht auf die Rechtskraft des Nichteintretensentscheides ab, sondern auf dessen Zustellung (<ref-ruling> E. 4d S. 52) beziehungsweise Eröffnung (<ref-ruling> E. 3 S. 82). Diese Auffassung stiess in der Lehre nicht auf Kritik, sondern wurde übernommen (PICHONNAZ, in: Commentaire romand, Code des obligations I, 1. Aufl. 2003 [Vorauflage], N. 12 zu aArt. 139 OR; DÄPPEN, in: Basler Kommentar, Obligationenrecht I, 4. Aufl. 2007 [Vorauflage], N. 9 zu aArt. 139 OR; BERTI, Zürcher Kommentar, 2002, N. 61 zu aArt. 139 OR; so schon VON TUHR/ESCHER, Allgemeiner Teil des Schweizerischen Obligationenrechts, Bd. II, 1974, S. 230; BUCHER, Schweizerisches Obligationenrecht, Allgemeiner Teil, 2. Aufl. 1988, S. 467), obwohl auch abweichende Auffassungen vertreten worden waren (OSER/SCHÖNENBERGER, Zürcher Kommentar, 2. Aufl. 1929, N. 3 zu Art. aArt. 139 OR; SPIRO, Die Begrenzung privater Rechte durch Verjährungs-, Verwirkungs- und Fatalfristen, Bd. I, 1975, S. 334). Hätte der Gesetzgeber mit der ZPO eine Abkehr von der zu aArt. 139 OR ergangenen Rechtsprechung bewirken wollen, hätte er dies im Gesetzestext und den Materialien zum Ausdruck gebracht. Daher besteht für das Bundesgericht kein Anlass, <ref-law> anders auszulegen als aArt. 139 OR, dessen Inhalt durch <ref-law> verallgemeinert wird.
2.8 Die Zustellung erfolgte am 5. August 2011, so dass sowohl die Frist von 30 Tagen zur Berufung nach <ref-law> als auch die Frist von einem Monat nach <ref-law> unter Berücksichtigung der Gerichtsferien vom 15. Juli bis und mit dem 15. August (<ref-law>) am 16. August 2011, dem ersten Tag nach Ende des Stillstandes (<ref-law>), zu laufen begannen. Die Frist von 30 Tagen zur Einreichung der Berufung endete am 14. September 2011, die Monatsfrist nach <ref-law> dagegen am 16. September 2011, dem Tag, der dieselbe Zahl trägt wie der Tag, an dem die Frist zu laufen begann (<ref-law>). Dem Beschwerdeführer verblieb demnach die gesamte Frist von 30 Tagen, um über die Ergreifung des Rechtsmittels zu entscheiden, bevor die Frist nach <ref-law> ablief. Damit kann offen bleiben, wie zu entscheiden wäre, wenn es sich anders verhielte, beispielsweise bei einer Zustellung eines Nichteintretensentscheides zwischen dem 30. Januar und dem 27. Februar (in diesem Zeitraum verstreicht die Monatsfrist vor Ablauf der Frist von 30 Tagen nach Art. 311 und Art. 321 ZPO) oder wenn für den Erhalt der Rechtshängigkeit nach <ref-law> eine kürzere Frist als die Rechtsmittelfrist vorgesehen ist. Aus <ref-ruling> kann diesbezüglich wohl nichts abgeleitet werden, da die mit Blick auf die Regelung der Aberkennungsklage massgebende Frist von damals 10 Tagen der Frist entsprach, in der nach § 261 der zürcherischen Zivilprozessordnung vom 13. Juni 1976 [kantonale] Berufung zu erklären gewesen wäre. Nachdem der Beschwerdeführer kein Rechtsmittel ergriffen hat, muss auch auf die Frage, wie es sich verhält, wenn gegen den Rückweisungsentscheid ein Rechtsmittel ergriffen wird (vgl. hierzu das zit. Urteil 4A_66/2012 E. 6), nicht näher eingegangen zu werden. Die Vorinstanz ging jedenfalls zu Recht davon aus, mit der Eingabe vom 17. Oktober 2011 habe der Beschwerdeführer die Frist von <ref-law> nicht gewahrt.
3. Der Beschwerdeführer beanstandet, dass die Vorinstanz der Beschwerdegegnerin eine Parteientschädigung zugesprochen hat. Die Beschwerdegegnerin habe die Anwendbarkeit von <ref-law> bei einem Nichteintretensentscheid mangels funktioneller Zuständigkeit bestritten, nicht die Einhaltung der Frist von <ref-law>, welche die Vorinstanz von Amtes wegen geprüft habe. Daher sei eine Parteientschädigung nicht gerechtfertigt.
3.1 Über die Reduktion der Parteientschädigung für das kantonale Verfahren könnte das Bundesgericht, sofern es den Einwand des Beschwerdeführers für begründet erachtet, selbst entscheiden, ohne dass eine Rückweisung an die Vorinstanz notwendig wäre. Insoweit fehlt es in formeller Hinsicht an einem materiellen Antrag und erweist sich der Rückweisungsantrag als ungenügend (<ref-ruling> E. 3.1 mit Hinweisen). Aus der Beschwerdebegründung ergibt sich allerdings auch ziffernmässig eindeutig, in welchem Sinn das Bundesgericht den angefochtenen Entscheid abändern soll. Selbst wenn man mit Blick darauf auf die Rüge eintritt, hilft dies dem Beschwerdeführer indessen nichts.
3.2 Die Prozesskosten (die Gerichtskosten und die Parteientschädigung; <ref-law>) werden in der Regel der unterliegenden Partei auferlegt (<ref-law>). Massgebend ist im erstinstanzlichen Verfahren, in welchem Mass die Parteien im Ergebnis mit ihren Rechtsbegehren durchdringen (RÜEGG, in: Basler Kommentar, a.a.O., N. 3 zu <ref-law>; TAPPY, in: CPC: Code de procédure civile commenté, a.a.O., N. 14 zu <ref-law>; vgl. für das Rechtsmittelverfahren vor Bundesgericht <ref-law>; Urteil des Bundesgerichts 5A_61/2012 vom 23. März 2012 E. 4 sowie <ref-ruling> E. 3, 159 E. 4, wonach Entschädigungen aufgrund des Obsiegens bzw. Unterliegens nach Massgabe der Anträge des Rechtsmittelklägers zu verlegen sind). Das Gericht kann von diesen Verteilungsgrundsätzen zwar unter bestimmten Voraussetzungen abweichen und die Prozesskosten nach Ermessen verteilen (<ref-law>). Aus der Tatsache, dass das Gericht die Argumentation der obsiegenden Partei verworfen und ihr nur aufgrund der Prüfung von Amtes wegen Recht gegeben hat, folgt jedoch nicht, dass es unbillig wäre (<ref-law>), ihr eine Parteientschädigung zuzusprechen (vgl. TAPPY, a.a.O., N. 15 zu <ref-law>). Eine Bundesrechtsverletzung ist nicht ersichtlich. Soweit der Beschwerdeführer beanstandet, die Vorinstanz hätte aufgrund der genannten Umstände ihren Nichteintretensentscheid nicht in "Gutheissung der Unzuständigkeitseinrede der Beklagten" fällen dürfen, verkennt er, dass der Nichteintretensentscheid nur aufgrund der Einrede der Beschwerdegegnerin ergehen konnte, da das angerufene Gericht zuständig wird, wenn sich die beklagte Partei ohne Einrede der fehlenden (örtlichen) Zuständigkeit zur Sache äussert (<ref-law>).
4. Schliesslich beruft sich der Beschwerdeführer auf <ref-law>, der für Klagen aus dem Betrieb einer Zweigniederlassung neben dem Gericht am Sitz der beklagten Partei wahlweise das Gericht am Ort der Niederlassung für zuständig erklärt. Dass die Klage im Zusammenhang mit der Zweigniederlassung stehe, könne nicht bestritten werden. Auf dem Anmeldeformular für die Mietliegenschaft werde schriftlich darauf hingewiesen, das Formular sei ausgefüllt an "Y._ AG in A._", einzusenden, was auch tatsächlich gemacht worden sei. Da die Beschwerdegegnerin von der heutigen Geschäftsniederlassung aus operativ tätig war und weiterhin sei und sich das Handeln ihres Vertreters anrechnen lassen müsse, stehe die Klage im Zusammenhang mit der Geschäftsniederlassung. Wenn die Beschwerdegegnerin an ihrem ehemaligen Hauptsitz eine Zweigniederlassung errichte, habe sie in Kauf zu nehmen, dass dort geklagt werde.
4.1 Der Beschwerdeführer trägt dem Bundesgericht seine eigene Auffassung der Rechts- und Sachlage vor. Auf die Argumentation der Vorinstanz geht er in keiner Weise ein. Damit genügt er den Begründungsanforderungen nicht (<ref-law>; <ref-ruling> E. 2.1 S. 245 f.; <ref-ruling> E. 3.3 S. 60).
4.2 Abgesehen davon existierte im Zeitpunkt der Mandatserteilung die Zweigniederlassung noch nicht. Das Formular "Anmeldung für eine Mietliegenschaft" datiert nach den Feststellungen der Vorinstanz vom 11. November 2009. Damals hatte die Beschwerdegegnerin ihren Sitz noch in A._ an dem auf dem Formular angegebenen Domizil. Das Formular gibt daher keinen Aufschluss darüber, ob die Abwicklung des Maklermandats nach der Sitzverlegung über die Zweigniederlassung A._ erfolgte. Damit zeigt der Beschwerdeführer nicht auf, dass sich die Klage aus dem Betrieb der Zweigniederlassung ergibt. Auch insoweit ist der angefochtene Entscheid nicht zu beanstanden.
5. Insgesamt erweist sich die Beschwerde als unbegründet. Sie ist abzuweisen, soweit darauf einzutreten ist. Dem Ausgang des Verfahrens entsprechend wird der Beschwerdeführer kostenpflichtig. Da sich die Beschwerdegegnerin nicht hat vernehmen lassen, steht ihr keine Parteientschädigung zu.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Es wird keine Parteientschädigung zugesprochen.
4. Dieses Urteil wird den Parteien und dem Handelsgericht des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 9. Oktober 2012
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Luczak