Sachverhalt: A. X._ (geb. 1964) stammt aus der Türkei. Er heiratete im Jahr 2002 die Schweizer Bürgerin V._ und reiste 2003 in die Schweiz ein. Das Ausländeramt des Kantons St. Gallen erteilte ihm in der Folge eine Aufenthalts- und am 6. Juni 2008 eine Niederlassungsbewilligung. Seit dem 30. September 2008 leben X._ und seine Schweizer Gattin getrennt. Am 8. Dezember 2008 ersuchte X._ um Nachzug seiner Kinder aus erster Ehe, nämlich Y._ (geb. 1992), Z._ (geb. 1994) und W._ (geb. 1996). Sie hielten sich zu jenem Zeitpunkt bei der Grossmutter väterlicherseits in der Türkei auf. Der Kanton St. Gallen wies die Nachzugsgesuche ab, wogegen X._ kein Rechtsmittel erhob. Die Grossmutter väterlicherseits verstarb im September 2009. B. Im Oktober 2009 zog X._ in den Kanton Zürich und stellte am 6. Juli 2010 beim Migrationsamt des Kantons Zürich erneut ein Nachzugsgesuch für seine Kinder. Das Migrationsamt lehnte das Gesuch am 9. Mai 2011 ab. Den dagegen erhobenen Rekurs wies die Sicherheitsdirektion des Kantons Zürich am 19. Januar 2012 ab. Eine hiergegen gerichtete Beschwerde an das Verwaltungsgericht des Kantons Zürich blieb erfolglos. C. Mit Eingabe vom 12. April 2012 beantragt X._, das Urteil des Verwaltungsgerichts des Kantons Zürich vom 13. März 2012 aufzuheben, dem Nachzugsgesuch sei - eventuell verbunden mit einer Integrationsvereinbarung - stattzugeben. Subeventualiter sei die Sache an die Vorinstanz zurückzuweisen. Das Verwaltungsgericht des Kantons Zürich hat darauf verzichtet, sich vernehmen zu lassen. Das Bundesamt für Migration beantragt, die Beschwerde abzuweisen.