Sachverhalt: A. Das Appellationsgericht geht von folgendem Sachverhalt aus: Anlässlich einer koordinierten Polizeikontrolle am 17. Juli 2007 in der "A._-Bar" fanden die beteiligten Beamten acht Brasilianerinnen und eine Bulgarin vor, die überwiegend nicht in der Schweiz angemeldet waren und in den Zimmern über der Bar logierten. Gemäss Appellationsgericht gingen diese Frauen in der Bar der Animation und in den darüber liegenden Zimmern der Prostitution nach. B. Der Strafgerichtspräsident des Kantons Basel-Stadt verurteilte X._ als verantwortliche Person für die "A._-Bar" sowie die darüber befindlichen Zimmer in Basel mit Urteil vom 19. Februar 2009 wegen mehrfacher Widerhandlung gegen fremdenpolizeiliche Vorschriften sowie mehrfachen Arbeitenlassens ohne Bewilligung im Wiederholungsfall zu einer Geldstrafe von 120 Tagessätzen zu Fr. 80.--, bedingt vollziehbar bei einer Probezeit von vier Jahren, sowie zu einer Busse von Fr. 30'000.--. Gegen dieses Urteil erklärte X._ Appellation beim Appellationsgericht des Kantons Basel-Stadt. Dieses verurteilte ihn wegen mehrfachen Arbeitenlassens ohne Bewilligung im Wiederholungsfall zu einer Geldstrafe von 120 Tagessätzen zu Fr. 80.--, bedingt vollziehbar bei einer Probezeit von vier Jahren, sowie zu einer Busse von Fr. 29'500.--. Von der Anklage der mehrfachen Widerhandlung gegen fremdenpolizeiliche Vorschriften sprach es ihn frei. C. X._ führt Beschwerde beim Bundesgericht. Er beantragt, das Urteil des Appellationsgerichts des Kantons Basel-Stadt vom 3. Dezember 2010 sei vollumfänglich aufzuheben, und er sei von Schuld und Strafe freizusprechen. Eventualiter sei das Urteil aufzuheben und die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Er beantragt ausserdem, der Beschwerde sei die aufschiebende Wirkung zu erteilen. D. Das Appellationsgericht des Kantons Basel-Stadt verzichtet auf eine Vernehmlassung; das Migrationsamt des Kantons Basel-Stadt beantragt sinngemäss, das vorinstanzliche Urteil zu bestätigen.