Sachverhalt: A. Der aus dem Kosovo stammende X._ (geb. 1971) reiste Anfang Dezember 1991 illegal in die Schweiz ein, wo er ein Asylgesuch stellte. Dieses wurde am 13. April 1992 abgelehnt und X._ aus der Schweiz weggewiesen. Im gleichen Entscheid wurde aber der Vollzug der Wegweisung gestützt auf den Bundesratsbeschluss vom 18. Dezember 1991 betreffend die vorläufige Aufnahme von Refraktären und Deserteuren aus Jugoslawien als unzumutbar bezeichnet und X._ vorläufig aufgenommen. Am 24. Mai 1996 heiratete er die italienische Staatsangehörige A._ (geb. 1962), die über eine Niederlassungsbewilligung im Kanton Basel-Stadt verfügte. In der Folge verzichtete er auf die vorläufige Aufnahme und erhielt eine Aufenthaltsbewilligung zum Verbleib bei der Ehefrau. Am 28. April 2000 wurde den Ehegatten das - im Juli 1999 - bereits aufgenommene Getrenntleben gerichtlich bewilligt. Die Ehe wurde mit Urteil vom 27. November 2002 geschieden. Am 20. Januar 2004 heiratete X._ seine Landsfrau B._ (geb. 1974), mit welcher er zwei im November 1999 bzw. im Juli 2001 geborene Kinder gezeugt hatte. Das Migrationsamt des Kantons Basel-Stadt verlängerte X._ jeweils die Aufenthaltsbewilligung und erteilte ihm im Juli 2007 sogar die Niederlassungsbewilligung. Am 11. Februar 2008 ersuchte dieser um den Nachzug seiner Ehefrau und der beiden gemeinsamen Kinder. Dieses Gesuch wurde zwecks vorheriger Überprüfung des weiteren Aufenthaltes von X._ sistiert. Dessen Niederlassungsbewilligung widerrief das kantonale Migrationsamt am 17. November 2008; gleichzeitig wies es ihn aus der Schweiz weg. Es warf ihm im Wesentlichen vor, er habe noch vor der gerichtlichen Trennung von der damaligen italienischen Ehefrau bereits eine Beziehung zu seiner heutigen Ehefrau aufgenommen und mit ihr das erste Kind gezeugt, was er den Schweizer Behörden seinerzeit verheimlicht habe. Die von X._ dagegen erhobenen kantonalen Rechtsmittel blieben erfolglos. B. Mit Beschwerde vom 8. April 2011 beantragt X._ dem Bundesgericht, den kantonal zuletzt ergangenen Entscheid des Appellationsgerichts des Kantons Basel-Stadt vom 10. Januar 2011 aufzuheben und dieses anzuweisen, die Niederlassungsbewilligung zu "verlängern". Das Appellationsgericht sowie das Bundesamt für Migration stellen Antrag auf Abweisung der Beschwerde. Das Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Das kantonale Migrationsamt hat sich nicht vernehmen lassen. Innert eingeräumter Frist hat sich X._ nicht mehr geäussert. C. Mit Verfügung vom 13. April 2011 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde hinsichtlich der Ausreiseverpflichtung von X._ antragsgemäss die aufschiebende Wirkung zuerkannt.