Sachverhalt: A. X._ (geb. 1948) ist kroatischer Staatsbürger. Von 1971 bis 1999 war er mit seiner Landsfrau A._ verheiratet; der Ehe entsprangen zwei inzwischen volljährige Kinder. Nach der Scheidung im August 1999 reiste X._ am 29. November 1999 in die Schweiz ein und heiratete gleichentags die Schweizerin B._, worauf ihm eine Aufenthaltsbewilligung zum Verbleib bei der Ehefrau und im Oktober 2004 die Niederlassungsbewilligung erteilt wurde. Am 12. Oktober 2005 liessen sich B._ und X._ scheiden, worauf sich dieser im Juni 2006 wiederum mit seiner ersten Ehefrau verheiratete und im August 2006 ohne Erfolg um die Bewilligung des Familiennachzugs ersuchte. Stattdessen widerrief das Migrationsamt Basel-Stadt mit Verfügung vom 7. März 2008 die Niederlassungsbewilligung von X._ und wies ihn aus der Schweiz weg. Es begründet dies damit, bei der Ehe mit B._ habe es sich um eine Scheinehe gehandelt, weshalb X._ seine Aufenthaltsbewilligung erschlichen habe. B. Gegen diesen Entscheid wehrte sich X._ erfolglos beim Justiz- und Sicherheitsdepartement sowie beim Regierungsrat des Kantons Basel-Stadt. Mit Urteil vom 27. November 2012 wies auch das Appellationsgericht des Kantons Basel-Stadt einen Rekurs von X._ ab. Das Gericht liess - gleich wie seine Vorinstanz - die Frage offen, ob es sich bei der Ehe von X._ mit B._ um eine Scheinehe gehandelt habe. Ungeachtet dessen habe er einen Widerrufsgrund gesetzt, indem er - unbestrittenermassen - bei der Erteilung der Niederlassungsbewilligung gegenüber dem Migrationsamt falsche Angaben gemacht habe, denn seine Erklärungen, wonach er die Behörden nicht habe täuschen wollen, seien unglaubhaft. Schliesslich könne er auch nicht als gut integriert gelten, weshalb der Widerruf der Niederlassungsbewilligung verhältnismässig sei. Die erneute Erteilung einer Aufenthaltsbewilligung komme ebenfalls nicht in Frage. C. Mit Beschwerde vom 7. Januar 2013 beantragt X._ dem Bundesgericht, das Urteil des Appellationsgerichts des Kantons Basel-Stadt aufzuheben und auf einen Widerruf der Niederlassungsbewilligung zu verzichten. Während das Appellationsgericht auf eine Vernehmlassung verzichtet, beantragen das Bundesamt für Migration und das Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt, die Beschwerde sei abzuweisen. Mit Verfügung vom 14. Januar 2013 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss die aufschiebende Wirkung zuerkannt.