Sachverhalt: A. Der mazedonische Staatsangehörige X._ (geb. ***1968) war von September 1991 bis September 1992 in Mazedonien mit seiner Landsfrau A._ verheiratet. Nach der Scheidung hielt sich X._ bis zu seiner Ausschaffung am 17. Februar 1995 illegal in der Schweiz auf. Im August 1995 heiratete er in Mazedonien eine 23 Jahre ältere Schweizer Bürgerin und reiste am 25. Mai 1997 zum Verbleib bei der Ehefrau in die Schweiz ein. Am 22. Mai 2002 wurde ihm die Niederlassungsbewilligung erteilt. Ein Gesuch um erleichterte Einbürgerung schrieb das Bundesamt für Migration am 6. Juni 2006 ab, nachdem es X._ mit dem Vorwurf, es könnte eine Scheinehe vorliegen, konfrontiert hatte und dieser sich nicht mehr vernehmen liess. Am 13. Dezember 2006 wurde die Ehe von X._ mit seiner schweizerischen Ehefrau geschieden. Mit der ersten Ehefrau A._ hat X._ zwei erst nach der Scheidung von der Kindsmutter geborene Kinder B._ (geb. ***1992) und C._ (geb. ***1996). Die Kinder leben bei ihrer Mutter und den Grosseltern in Mazedonien. Mit Urteil des Kreisgerichts Tetowo vom 20. Juni 2005 wurden sie unter das Sorgerecht des Vaters gestellt. B. Am 22. April 2005 stellte X._ ein erstes Gesuch um Nachzug der Kinder, das vom Migrationsamt des Kantons Basel-Stadt am 3. März 2006 abgewiesen wurde. Das Sicherheitsdepartement (heute Justiz- und Sicherheitsdepartement) sowie das Appellationsgericht des Kantons Basel-Stadt (Urteil vom 20. April 2007) haben diesen Entscheid bestätigt. Am 22. Oktober 2008 stellte X._ erneut ein Gesuch um Nachzug seiner beiden Kinder. Zur Begründung führte er im Wesentlichen aus, nach dem am 1. Januar 2008 in Kraft getretenen Ausländergesetz dürfe beim Familiennachzug nicht mehr zwischen gemeinsam und getrennt lebenden Eltern unterschieden werden. Das Migrationsamt trat mit Verfügung vom 4. Dezember 2008 mangels neuer Tatsachen auf das Gesuch nicht ein. Das Justiz- und Sicherheitsdepartement wies den Rekurs gegen den Nichteintretensentscheid mit Entscheid vom 30. Juni 2008 (recte 30. Juni 2009) ab. Die dagegen erhobene Beschwerde wies das Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht mit Urteil vom 23. November 2009 (zugestellt am 18. Januar 2010) ebenfalls ab. Die kantonalen Rechtsmittelinstanzen gingen davon aus, dass die Anwendung des neuen Rechts zu keinem andern Ergebnis geführt hätte. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 16. Februar 2010 beantragt X._, die Verfügung des Migrationsamts des Kantons Basel-Stadt vom 4. Dezember 2008 aufzuheben und den Kindern B._ und C._ die Einreise und den Aufenthalt in der Schweiz zu bewilligen, eventualiter das Sicherheitsdepartement (Migrationsamt) anzuweisen, das Familiennachzugsgesuch materiell zu entscheiden. Mit Eingabe vom 17. Februar 2010 änderte der Beschwerdeführer das Rechtsbegehren insofern, als mit der eingereichten Beschwerde einzig die Aufhebung des Urteils des Appellationsgerichts des Kantons Basel-Stadt vom 23. November 2009 beantragt wird. Das Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt schliesst auf Abweisung der Beschwerde. Das Appellationsgericht des Kantons Basel-Stadt hat auf Vernehmlassung verzichtet. Das Migrationsamt des Kantons Basel-Stadt liess sich nicht vernehmen. Das Bundesamt für Migration hat unter Verweis auf die neueste Rechtsprechung des Bundesgerichts auf einen Antrag verzichtet.