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.

Erwägungen:
1. Gegen den angefochtenen kantonal letztinstanzlichen Endentscheid über den Widerruf der Niederlassungsbewilligung ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht zulässig, weil grundsätzlich ein Anspruch auf das Fortbestehen dieser Bewilligung gegeben ist (vgl. Art. 83 lit. c Ziff. 2, Art. 86 Abs. 1 lit. d sowie Art. 90 BGG; <ref-ruling> E. 1.2.1 S. 4).
2. Nach dem hier anwendbaren Bundesgesetz vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20; vgl. nicht publizierte E. 1 von <ref-ruling> mit Hinweisen) kann die Niederlassungsbewilligung widerrufen werden, wenn der Ausländer oder sein Vertreter im Bewilligungsverfahren falsche Angaben macht oder wesentliche Tatsachen verschwiegen hat (Art. 63 Abs. 1 lit. a in Verbindung mit Art. 62 lit. a AuG). Hierauf stützen sich die Vorinstanzen. Der Widerruf ist allerdings nur zulässig, wenn er aufgrund der relevanten Gesamtumstände verhältnismässig ist. Das bestreitet der Beschwerdeführer.
3. 3.1 Gemäss Art. 63 Abs. 2 AuG kann die Niederlassungsbewilligung von Ausländern, die sich seit mehr als 15 Jahren ununterbrochen und ordnungsgemäss in der Schweiz aufhalten, nur aus Gründen von Art. 63 Abs. 1 lit. b (schwerwiegender Verstoss oder Gefährdung der öffentlichen Sicherheit und Ordnung) oder Art. 62 lit. b AuG (Verurteilung zu einer längerfristigen Freiheitsstrafe) widerrufen werden. Demnach ist nach Ablauf dieser Zeit ein Widerruf gestützt auf Art. 62 lit. a AuG wegen falscher Angaben oder Verschweigens wesentlicher Tatsachen nicht mehr möglich. Insoweit sieht der Gesetzgeber einen Widerruf als unverhältnismässig an (vgl. <ref-ruling> E. 4.3 S. 13 sowie die nicht amtlich publizierte E. 5; Botschaft zum AuG in BBl 2002 S. 3810 f. und Berichterstatterin Leuthard in AB 2004 N 1089). Für die Anwendbarkeit von Art. 63 Abs. 2 AuG ist entscheidend, dass die erwähnten 15 Jahre bis zur erstinstanzlichen Verfügung des Widerrufs erfüllt werden (<ref-ruling> E. 4.2 S. 12).
Es fragt sich, ob die Zeit zwischen der Einreise des Beschwerdeführers oder zumindest ab seiner Anerkennung als vorläufig Aufgenommener im Rahmen von Art. 63 Abs. 2 AuG zu berücksichtigen ist. Dann käme er auf einen anrechenbaren Aufenthalt von knapp 17 Jahren bzw. von rund 16 Jahren und sieben Monaten. Damit wäre ein auf Art. 62 lit. a AuG gestützter Widerruf der Niederlassungsbewilligung gemäss Art. 63 Abs. 2 AuG ausgeschlossen.
3.2 Die Vorinstanz ist der Auffassung, der Beschwerdeführer könne sich nicht auf Art. 63 Abs. 2 AuG berufen. Es sei höchstens die Zeit ab Eheschliessung mit der italienischen Staatsangehörigen am 24. Mai 1996 als ordnungsgemässer Aufenthalt zu berücksichtigen. Bis zum massgeblichen Zeitpunkt des Widerrufs der Bewilligung am 17. November 2008 seien insoweit aber nur rund zwölfeinhalb Jahre vergangen. Der Zeitraum zwischen der Einreise in die Schweiz im Dezember 1991 bzw. ab der vorläufigen Aufnahme im April 1992 und der Heirat im Mai 1996 sei nicht einzubeziehen. Denn damals habe er nicht über eine ordentliche ausländerrechtliche Kurzaufenthalts- oder Aufenthaltsbewilligung verfügt, wie das gemäss den Weisungen des Bundesamtes für Migration verlangt werde (vgl. Ziff. 3.4.6 in fine und Ziff. 8.3.2 lit. d der erwähnten Weisungen "I. Ausländerbereich", Version vom 30. September 2011).
4. Die Frage, ob die vorläufige Aufnahme als ordnungsgemässer Aufenthalt im Sinne von Art. 63 Abs. 2 AuG anzusehen ist, kann offen gelassen werden. Denn die Beschwerde ist ungeachtet dessen gutzuheissen.
Zum einen sollen Niederlassungsbewilligungen nur nach nochmaliger eingehender Prüfung des bisherigen Verhaltens des Ausländers erteilt werden (vgl. Art. 60 der Verordnung vom 24. Oktober 2007 über Zulassung, Aufenthalt und Erwerbstätigkeit [VZAE; SR 142.201] bzw. Art. 11 Abs. 1 der Vollziehungsverordnung vom 1. März 1949 zum ANAG [ANAV; AS 1949 I 228]). Zum anderen wusste die kantonale Ausländerbehörde vorliegend bereits im Frühjahr 2000, dass der Beschwerdeführer schon im Jahre 1998 mehrere Monate von seiner damaligen italienischen Ehefrau getrennt gelebt hatte und die Eheleute seit Juli 1999 wieder getrennt waren. In einer Übersicht vom 14. November 2000 hielt die Behörde fest, der Beschwerdeführer habe mit seiner italienischen Ehefrau (nur) während zwei Jahren zusammengelebt. Dennoch verlängerte sie ihm damals die Aufenthaltsbewilligung weiterhin, obwohl hierauf aufgrund ihres Kenntnisstandes mangels Zusammenlebens bereits kein Anspruch mehr bestand (vgl. Art. 17 Abs. 2 Satz 1 ANAG). Selbst als die italienische Ehefrau im Januar 2001 schriftlich mitteilte, inzwischen habe der Beschwerdeführer in seiner Heimat "nochmal geheiratet" und aus jener Beziehung sei ein Kind auf die Welt gekommen, reagierte die Ausländerbehörde nicht und sprach den Beschwerdeführer auch nicht hierauf an. Vielmehr verlängerte sie - auch nach der im Jahr 2002 ausgesprochenen Ehescheidung - weiterhin die Aufenthaltsbewilligung. Im Jahr 2004 unterrichtete der Beschwerdeführer das Migrationsamt von der im selben Jahr in seiner Heimat mit seiner Landsfrau erfolgten Eheschliessung. Im Juli 2007 erteilte das Migrationsamt dem Beschwerdeführer - auf seinen Antrag um Erneuerung der Aufenthaltsbewilligung hin - die Niederlassungsbewilligung. Als die Ausländerbehörde die Bewilligung im November 2008 widerrief, hielt sich der Beschwerdeführer seit fast 17 Jahren in der Schweiz auf. Aufgrund ihrer Kenntnisse hätte die Behörde rund acht Jahre früher den Aufenthalt des Beschwerdeführers beenden können. Sie unternahm jedoch nichts dergleichen. Auch ging sie den damaligen Hinweisen auf die aussereheliche Beziehung und Geburt von Kindern nicht nach. Der Beschwerdeführer geht seit Jahren einer geregelten Arbeit nach, ist beruflich gut integriert und hat keine Sozialhilfe bezogen.
Mit Blick auf die Gesamtumstände erweist es sich als unverhältnismässig, wenn die Behörden dem Beschwerdeführer erst im November 2008 wegen Verschweigens der Geburt der Kinder sowie der ausserehelichen Beziehung zu seiner aktuellen Ehefrau die Niederlassungsbewilligung widerrufen (vgl. auch Urteile des Bundesgerichts 2C_403/2011 vom 2. Dezember 2011 E. 3.3-3.5; 2A_46/2002 vom 23. Mai 2002 E. 3.4). Daran ändern die beiden strafrechtlichen Verurteilungen aus den Jahren 2003 und 2005 zu jeweils bedingt vollziehbaren Gefängnisstrafen von vier Monaten - woraufhin die Behörden den Beschwerdeführer fremdenpolizeilich verwarnten, jedoch weiterhin keine Entfernungsmassnahmen ergriffen - nichts. Sollte sich Letzterer allerdings wieder etwas zuschulden kommen lassen, könnten die Behörden einen auf Art. 63 Abs. 1 lit. b oder Art. 62 lit. b AuG gestützten Widerruf erwägen, wobei sie dessen gesamtes bisheriges Verhalten mitzuberücksichtigen hätten.
5. 5.1 Demzufolge ist die Beschwerde gutzuheissen und der angefochtene Entscheid des Appellationsgerichts aufzuheben. Die Niederlassungsbewilligung ist nicht zu widerrufen. Ob dem Beschwerdeführer der begehrte Familiennachzug zu bewilligen ist, bildet vorliegend nicht Verfahrensgegenstand. Darüber werden die Behörden in Anwendung der einschlägigen Bestimmungen noch zu befinden haben.
5.2 Die Sache ist zur Neuverlegung der Kosten- und Entschädigungsfolgen des Verfahrens bei den kantonalen Instanzen an das Appellationsgericht zurückzuweisen (Art. 67 und Art. 68 Abs. 5 BGG). Bei diesem Ausgang sind keine Kosten für das bundesgerichtliche Verfahren zu erheben (Art. 66 Abs. 1 und 4 BGG) und es ist dem Beschwerdeführer eine angemessene Parteientschädigung zuzusprechen (Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen und das Urteil des Appellationsgerichts des Kantons Basel-Stadt als Verwaltungsgericht vom 10. Januar 2011 aufgehoben. Die Niederlassungsbewilligung wird nicht widerrufen.
2. Es werden keine Gerichtskosten erhoben.
3. Der Kanton Basel-Stadt hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4. Dieses Urteil wird den Verfahrensbeteiligten, dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 7. März 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Merz