Sachverhalt: A. Der serbische Staatsangehörige X._ (geb. 1973) reiste 1999 illegal in die Schweiz ein und stellte hier erfolglos ein Asylgesuch. Am 1. Juni 2001 heiratete er eine Schweizerin und erhielt in der Folge eine Aufenthaltsbewilligung für den Kanton St. Gallen. Nach der Ehescheidung verweigerte der Kanton Zürich den Zuzug bzw. die Erteilung einer Aufenthaltsbewilligung. Am 26. April 2003 heiratete X._ in seiner Heimat eine 25 Jahre ältere, in der Schweiz aufenthaltsberechtigte Landsfrau und erhielt in der Folge eine letztmals bis 26. Januar 2006 verlängerte Aufenthaltsbewilligung für den Kanton Zürich. Im Anschluss an die Trennung von seiner zweiten Ehefrau verweigerte der Kanton Zürich die Verlängerung der Aufenthaltsbewilligung. Am 12. Juli 2009 reiste X._ mit einem Schengen-Visum C erneut in die Schweiz ein und heiratete am 24. Juli 2009 in Zürich die hier niedergelassene Landsfrau Y._ (geb. 1978). X._ erwirkte in der Schweiz in der Zeit zwischen 1999 und 2010 sieben rechtskräftige Verurteilungen, hauptsächlich wegen Verkehrsdelikten: - Am 30. März 1999 verurteilte ihn die Bezirksanwaltschaft Zürich zu einer Gefängnisstrafe von 30 Tagen bedingt wegen rechtswidriger Einreise. - Mit Strafbefehl der Bezirksanwaltschaft Zürich vom 11. April 2000 wurde X._ zu einer Gefängnisstrafe von 10 Tagen bedingt wegen Fahrens in angetrunkenem Zustand und (einfacher) Verletzung von Verkehrsregeln verurteilt. - Am 19. April 2005 verurteilte ihn die Staatsanwaltschaft Zürich-Limmat zu einer Gefängnisstrafe von 45 Tagen bedingt und einer Busse von Fr. 1'800.-- wegen Vereitelung einer Blutprobe, grober und einfacher Verkehrsregelverletzung und pflichtwidrigen Verhaltens bei Unfall. - Mit Strafbefehl der Staatsanwaltschaft See-Oberland vom 10. März 2006 wurde X._ zu einer Gefängnisstrafe von 3 Monaten unbedingt wegen Fahrens in fahrunfähigem Zustand und einfacher Verkehrsregelverletzung verurteilt. - Am 3. Juni 2008 verurteilte ihn das Bezirksgericht Bülach zu einer Geldstrafe von 180 Tagessätzen zu Fr. 30.-- (unter Einbezug der widerrufenen bedingten Freiheitsstrafe von 45 Tagen) wegen Fahrens in fahrunfähigem Zustand. - Mit Urteil des Bezirksgerichts Zürich vom 13. April 2010 wurde X._ zu einer Geldstrafe von 90 Tagessätzen zu Fr. 40.-- wegen versuchter Täuschung der Behörden im Sinn von Art. 118 Abs. 1 AuG (SR 142.20) verurteilt. - Am 28. September 2010 verurteilte ihn das Bezirksgericht Zürich zu einer Geldstrafe von 120 Tagessätzen zu Fr. 40.-- wegen mehrfachen Fahrens trotz Führerausweisentzug sowie des Versuchs dazu. Am 30. April 2012 ist X._ der Führerausweis unter Auflage konsequenter und vollständiger Alkoholabstinenz und einer Kontrolluntersuchung im Juli 2012 wieder erteilt worden. B. Am 30. November 2009 wies die Sicherheitsdirektion des Kantons Zürich das Gesuch von X._ um Erteilung einer Aufenthaltsbewilligung vom 27. Juli 2009 ab und wies ihn aus der Schweiz weg. Den dagegen erhobenen Rekurs wies der Regierungsrat des Kantons Zürich mit Beschluss vom 15. August 2012 ab. Die anschliessende Beschwerde an das Verwaltungsgericht des Kantons Zürich blieb erfolglos (Urteil vom 9. Januar 2013). C. Vor Bundesgericht beantragt X._, das Urteil des Verwaltungsgerichts des Kantons Zürich vom 9. Januar 2013 aufzuheben und ihm eine Aufenthaltsbewilligung für den Kanton Zürich zu erteilen sowie den Verbleib in der Schweiz zu gestatten. Das Verwaltungsgericht des Kantons Zürich verzichtet auf eine Vernehmlassung. Der Regierungsrat des Kantons Zürich und das Bundesamt für Migration (BFM) beantragen die Abweisung der Beschwerde. Am 19. Februar 2013 hat der Abteilungspräsident der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt.