Sachverhalt: A. Der aus der Türkei stammende X._ (geb. 1966) lebt seit 2005 in der Schweiz, wo er sich bereits zuvor zwischen 1989 und 2002 aufgehalten hat. Vom 16. Februar 1999 bis zum 24. April 2002 war er mit der türkischen Staatsangehörigen Y._ verheiratet. Aus dieser Beziehung gingen drei Kinder hervor, darunter der am 11. September 1994 geborene Z._ sowie der am 17. Januar 1998 geborene W._. Die beiden Söhne leben in der Türkei, wurden dort nach der Scheidung ihrer Eltern zunächst von der Mutter und zuletzt von den Grosseltern, d.h. den Eltern von X._, betreut. Mit Urteil vom 15. Januar 2010 hat das Bezirksgericht A._ (Türkei) die elterliche Sorge für die beiden Söhne von der Mutter Y._ auf den Vater X._ übertragen. Aufgrund gesundheitlicher Probleme können die Grosseltern ihren Betreuungsaufgaben nicht mehr nachkommen. Am 14. Juni 2002 heiratete X._ die Schweizer Bürgerin V._ (geb. 1944). Nach der Rückkehr in die Schweiz im Jahr 2005 erhielt X._ zunächst eine Aufenthaltsbewilligung und anschliessend eine Niederlassungsbewilligung; am 31. Januar 2011 wurde er eingebürgert. B. Mit Verfügung vom 14. Juli 2011 wies das Migrationsamt des Kantons Zürich das Nachzugsgesuch für Z._ und W._ ab. Die dagegen von X._ erhobenen kantonalen Rechtsmittel blieben erfolglos. C. Vor Bundesgericht beantragt X._, das Urteil des Verwaltungsgerichts des Kantons Zürich vom 9. Mai 2012 aufzuheben und das Gesuch um Einreise und Aufenthaltsbewilligung (Familiennachzug) für die Söhne Z._ und W._ gutzuheissen. Das Verwaltungsgericht des Kantons Zürich verzichtete auf eine Vernehmlassung. Die Sicherheitsdirektion des Kantons Zürich und das Bundesamt für Migration beantragen die Abweisung der Beschwerde. 