Sachverhalt: A. Der Polizist X._ nahm am 16. April 2007 gemeinsam mit einem Kollegen im Eingangsbereich der Internationalen Uhren- und Schmuckmesse in Basel einen Mann wegen des Verdachts des Taschendiebstahls zum Nachteil eines russischen Messegastes fest. Er legte dem Mann Handfesseln an und stellte anhand des Ausweises fest, dass es sich um einen algerischen Asylbewerber handelte. Er beschimpfte den Festgenommenen lautstark in Anwesenheit einer anwachsenden Menschenmenge mit verschiedenen Ausdrücken, unter anderem als "Sauausländer" und "Dreckasylant". B. Das Strafgericht des Kantons Basel-Stadt, Einzelgericht, sprach X._ am 25. Oktober 2011 der Rassendiskriminierung (Art. 261bis Abs. 4 StGB) schuldig und verurteilte ihn zu einer Geldstrafe von 60 Tagessätzen zu Fr. 200.--, bedingt vollziehbar bei einer Probezeit von zwei Jahren. Vom Vorwurf des Amtsmissbrauchs sprach es ihn frei. X._ beantragte mit Berufung, er sei freizusprechen. Die Staatsanwaltschaft erhob Anschlussberufung und beantragte die Bestätigung des erstinstanzlichen Urteils im Schuldpunkt und eine Erhöhung der Strafe. Das Appellationsgericht des Kantons Basel-Stadt, Ausschuss, bestätigte mit Urteil vom 21. September 2012 den erstinstanzlichen Entscheid. C. X._ führt Beschwerde in Strafsachen. Er beantragt, das Urteil des Appellationsgerichts sei aufzuheben und er sei freizusprechen. Eventualiter sei die Sache zur neuen Entscheidung an die Vorinstanz zurückzuweisen. D. Das Appellationsgericht hat auf eine Vernehmlassung verzichtet und beantragt unter Hinweis auf das angefochtene Urteil die Abweisung der Beschwerde. Die Staatsanwaltschaft hat sich nicht vernehmen lassen. 