Sachverhalt: A. A.A._ (geb. 1973) stammt aus Mazedonien. Er hielt sich zwischen 1992 und 1996 als Saisonnier in der Schweiz auf. Nachdem er das Land zwischenzeitlich verlassen hatte, reiste er 1998 wieder in die Schweiz ein und heiratete am 17. Juli 1998 die Schweizerin C._ (geb. 1945). Weil die Ehe als Scheinehe eingestuft wurde, erhielt er keine Aufenthaltsbewilligung und musste die Schweiz wieder verlassen. Die Ehe wurde am 23. Dezember 1999 geschieden. C._ verstarb im Jahr 2000. Am 6. Mai 2001 reiste A.A._ erneut in die Schweiz ein und ersuchte um Asyl. Am 14. Februar 2002 heiratete er die Schweizerin D._ und erhielt am 5. April 2002 eine Aufenthaltsbewilligung zum Verbleib bei seiner Ehefrau. Sein Asylgesuch wurde als gegenstandslos abgeschrieben. Am 24. Mai 2007 erhielt er die Niederlassungsbewilligung; am 6. Oktober 2010 wurde die Ehe geschieden. Am 15. Juli 2011 heiratete A.A._ in Mazedonien seine Landsfrau B._ (geb. 1973). Am 18. Oktober 2011 stellte er ein Gesuch um Familiennachzug für seine Frau und die drei gemeinsamen Kinder B.A._ (geb. 28. Dezember 1997), C.A._ (geb. 26. August 2001) und D.A._ (geb. 5. Mai 2011). Daraufhin widerrief das Migrationsamt mit Verfügung vom 19. März 2012 seine Niederlassungsbewilligung, wies ihn aus der Schweiz weg und lehnte das Gesuch um Familiennachzug ab. B. Ein hiergegen an die Sicherheitsdirektion gerichteter Rekurs blieb erfolglos. Die gegen deren Entscheid beim Verwaltungsgericht des Kantons Zürich erhobene Beschwerde wies dieses mit Urteil vom 19. Dezember 2012 ab. C. Mit Eingabe vom 28. Februar 2013 beantragen A.A._ (Beschwerdeführer 1), B._ und die gemeinsamen Kinder (Beschwerdeführerinnen 2-5) dem Bundesgericht, das Urteil des Verwaltungsgerichts (Vorinstanz) vom 19. Dezember 2012 aufzuheben. Das Verwaltungsgericht des Kantons Zürich und das Bundesamt für Migration beantragen, die Beschwerde abzuweisen. Mit Verfügung vom 5. März 2013 hat der Präsident der II. öffentlich-rechtlichen Abteilung der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt.