Sachverhalt: A. A.a. A.X._ (geb. 1965) ist Staatsangehöriger der Republik Côte d'Ivoire und reiste am 27. September 1999 in die Schweiz ein, wo er um Asyl ersuchte. Am 8. Februar 2000 heiratete er die Schweizer Bürgerin B.Y._ (geb. 1953) und erhielt in der Folge eine Aufenthaltsbewilligung für den Kanton Solothurn. Ab April 2001 lebte das Ehepaar getrennt. Am 14. Januar 2004 wurde die Verlängerung der Aufenthaltsbewilligung von A.X._ verweigert, weil die Ehegemeinschaft aufgegeben worden sei. Nachdem das Ehepaar X.Y._ das Eheleben wieder aufgenommen hatte, wurde diese Verfügung am 26. Januar 2004 in Wiedererwägung gezogen. Am 28. November 2005 erteilte die Solothurner Ausländerbehörde A.X._ nach erneuter Untersuchung der Eheverhältnisse die Niederlassungsbewilligung. Zu diesem Zeitpunkt war der Behörde bekannt, dass A.X._ in seiner Heimat mit seiner Landsfrau C._ (geb. 1979) vier Kinder hatte, wovon eines während der Ehe mit B.Y._ am 20. Juli 2001 geboren wurde. A.b. Am 1. August 2006 zog A.X._ in den Kanton Aargau, wo ihm die Erteilung einer Niederlassungsbewilligung verweigert wurde. Am 9. November 2006 teilte B.Y._ den Solothurner Behörden mit, dass sie sich von ihrem Mann getrennt habe. Am 6. September 2007 ging aus der Beziehung mit C._ mit Tochter D._ das fünfte Kind von A.X._ hervor. A.c. Am 3. September 2008 stellte A.X._ ein Gesuch um Kantonswechsel in den Kanton Zürich. Dieses Gesuch wurde bewilligt und er erhielt eine Niederlassungsbewilligung mit Kontrollfrist bis zum 28. Februar 2013. Die Ehe X.Y._ wurde am 19. Mai 2009 geschieden. Am 28. September 2010 verheiratete sich A.X._ mit C._ und beantragte am 23. Mai 2011 zunächst die Einreisebewilligung für seine Ehegattin und vier gemeinsame Kinder; später beschränkte er das Nachzugsgesuch auf seine Ehegattin und die Tochter D._. B. Das Migrationsamt des Kantons Zürich widerrief mit Verfügung vom 4. Oktober 2011 die Niederlassungsbewilligung von A.X._ und setzte ihm Frist zum Verlassen der Schweiz. Zudem wies es die Familiennachzugsgesuche für die Ehefrau und die Tochter D._ ab. Die hiergegen erhobenen Rechtsmittel an die Sicherheitsdirektion und das Verwaltungsgericht des Kantons Zürich blieben erfolglos. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 2. Mai 2013 beantragt A.X._, das angefochtene Urteil des Verwaltungsgerichts des Kantons Zürich vom 27. März 2013 sei aufzuheben und ihm die Niederlassungsbewilligung zu belassen. Eventualiter sei ihm die Jahresaufenthaltsbewilligung zu erteilen. Das Verwaltungsgericht des Kantons Zürich und das Bundesamt für Migration schliessen auf Abweisung der Beschwerde. Die Sicherheitsdirektion des Kantons Zürich verzichtet auf eine Vernehmlassung.