Sachverhalt: A. Am 26. April 2012 hat der aus dem Kosovo stammende X._ (geb. 1952) in seinem Herkunftsland die kosovarische Staatsangehörige A._ (geb. 1972) geheiratet. Bereits vorgängig hatte A._ am 17. Oktober 2011 ein Gesuch um Einreise zur Ehevorbereitung gestellt, wobei die Brautleute zu diesem Zeitpunkt einzig telefonisch und auf elektronischem Weg miteinander kommuniziert hatten und eine erste persönliche Begegnung noch ausstand. Nach erfolgter Heirat reichte A._ am 24. Mai 2012 ein Gesuch um Familiennachzug ein. B. Mit Verfügung vom 30. März 2012 wies das Migrationsamt des Kantons Zürich das Gesuch um Einreise zur Ehevorbereitung ab, da von einem rechtsmissbräuchlichen Handeln auszugehen sei und folglich nach dem Eheschluss kein Anspruch auf eine Aufenthaltsbewilligung bestehe. Im anschliessenden Rekursverfahren verneinte die Sicherheitsdirektion des Kantons Zürich, welcher das Gesuch vom 24. Mai 2012 zuständigkeitshalber überwiesen wurde, mit Entscheid vom 30. Juli 2012 einen Anspruch auf Familiennachzug und wies den Rekurs ab. Die dagegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons Zürich mit Urteil vom 20. Dezember 2012 ab. Im Verlaufe des Beschwerdeverfahrens wurde X._ eingebürgert. C. Vor Bundesgericht beantragt X._, das Urteil des Verwaltungsgerichts des Kantons Zürich vom 20. Dezember 2012 aufzuheben und das Migrationsamt des Kantons Zürich anzuweisen, A._ den Familiennachzug zu bewilligen. Ferner sei ihm die unentgeltliche Rechtspflege zu gewähren. Die Sicherheitsdirektion des Kantons Zürich und das Bundesamt für Migration (BFM) beantragen die Abweisung der Beschwerde. Das Verwaltungsgericht des Kantons Zürich verzichtete auf eine Vernehmlassung. 