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.

Erwägungen:
1. Das vorinstanzliche Urteil erging am 3. Dezember 2010. In Bezug auf die Frage des anwendbaren Prozessrechts ist noch die bis zum 31. Dezember 2010 in Kraft stehende Strafprozessordnung des Kantons Basel-Stadt anwendbar (Art. 453 Abs. 1 der Schweizerischen Strafprozessordnung vom 5. Oktober 2007 [StPO, SR 312.0]).
1.1 Der Beschwerdeführer rügt die Missachtung des Anspruchs auf rechtliches Gehör sowie grundlegender Verfahrensgarantien im Verfahren vor den kantonalen Instanzen. Soweit sich seine Vorbringen auf das Urteil der ersten Instanz beziehen, ist der kantonale Instanzenzug nicht erschöpft bzw. der Entscheid nicht letztinstanzlich im Sinne von <ref-law> (Urteil des Bundesgerichts 6B_1078/2009 vom 13. Dezember 2010 E. 2.5 mit Hinweis). Hierauf ist nicht einzutreten.
1.2 Der Beschwerdeführer beanstandet, die Vorinstanz habe die ihn entlastenden Aussagen sowie die Verfahrensfehler der ersten Instanz nicht angemessen berücksichtigt. Die Einvernahmen der Belastungszeuginnen hätten ohne seine Anwesenheit stattgefunden. Eine Konfrontation sei unterblieben. Dies stelle eine Verletzung des rechtlichen Gehörs dar (<ref-law> und Art. 6 Abs. 3 lit. d EMRK). Die Entscheidung der ersten Instanz, diese Aussagen lediglich als Indizien zu werten, sei keine rechtlich tragbare Lösung. Die Aussagen hätten nicht verwendet werden dürfen, und die Vorinstanz hätte das erstinstanzliche Urteil aufheben müssen (Beschwerde, S. 6 ff.).
1.3 Die Vorinstanz äussert sich nicht zur bereits in der Appellationsbegründung geäusserten fehlenden Konfrontation (pag. 229 f. der Vorakten). Die Argumentation des Beschwerdeführers geht allerdings an der Sache vorbei.
Nach der Verfahrensgarantie von Art. 6 Ziff. 3 lit. d EMRK hat der Angeschuldigte Anspruch darauf, dem Belastungszeugen Fragen zu stellen. Dieser Anspruch ist ein besonderer Aspekt des Rechts auf ein faires Verfahren nach Art. 6 Ziff. 1 EMRK. Eine belastende Zeugenaussage ist somit grundsätzlich nur verwertbar, wenn der Beschuldigte wenigstens einmal während des Verfahrens angemessen und hinreichend Gelegenheit hatte, das Zeugnis in Zweifel zu ziehen und Fragen an den Zeugen zu stellen, wobei als Zeugenaussagen auch in der Voruntersuchung gemachte Aussagen vor Polizeiorganen gelten. Der Beschuldigte muss namentlich in der Lage sein, die Glaubhaftigkeit einer Aussage zu prüfen und den Beweiswert in kontradiktorischer Weise auf die Probe und in Frage zu stellen (zum Ganzen <ref-ruling> E. 3.1).
1.4 Wie die erste Instanz zu Recht festhält (erstinstanzliches Urteil, S. 9), kann unter besonderen Umständen auf eine Konfrontation des Beschwerdeführers mit den Belastungszeuginnen oder auf eine ergänzende Befragung dieser Zeuginnen verzichtet werden (ausführlich BGE 131 IV 476 E. 2.2; <ref-ruling> E. 5b; je mit Hinweisen).
So ist die fehlende Befragung nicht zu beanstanden, wenn ein Zeuge berechtigterweise sein Zeugnis verweigert, der Zeuge trotz angemessener Nachforschung unauffindbar bleibt oder in der Zwischenzeit verstorben ist. In solchen Fällen ist gestützt auf Art. 6 Ziff. 1 und Ziff. 3 lit. d EMRK erforderlich, dass der Beschuldigte zum streitigen Zeugnis hinreichend Stellung nehmen kann, die Aussagen sorgfältig geprüft werden und der Schuldspruch nicht alleine darauf abgestützt wird (<ref-ruling> E. 2.2; <ref-ruling> E. 3.1; <ref-ruling> E. 6a je mit Hinweisen).
1.5 Das Fragerecht steht dem Beschuldigten nicht höchstpersönlich, sondern allgemein der Verteidigung zu. Auf das Recht der Befragung von Belastungszeugen kann auch verzichtet werden. Ein derartiger Verzicht führt dazu, dass die in der Untersuchung gemachten Aussagen der Zeugen verwendet werden dürfen (<ref-ruling> E. 1b mit Hinweisen). Eine Verwertung kann entsprechend auch stattfinden, wenn der Verteidiger auf die persönliche Anwesenheit des Beschwerdeführers verzichtet.
1.6 Im vorliegenden Fall legte die erste Instanz dar, dass die unentschuldigt nicht zur erstinstanzlichen Hauptverhandlung erschienenen Frauen nach der verfügten Ausreise und Einreisesperre sowie aufgrund des unbekannten Aufenthaltsortes nicht mehr befragt werden könnten. Die hierauf von der Verteidigerin beantragte und vom Gericht bewilligte Dispensation ihrer Mandantinnen, die sie vorgängig wiederholt vergeblich zu kontaktieren versucht hatte, stellte der Beschwerdeführer - ohne Wortmeldung - nicht in Frage (vgl. Protokoll erstinstanzliche Hauptverhandlung).
Die Vorinstanz hätte zwar auf die - gerügte - Thematik der fehlenden Konfrontationseinvernahmen eingehen sollen. Im Ergebnis verletzt sie aber kein Bundes- oder Konventionsrecht.
2. 2.1 Der Beschwerdeführer rügt sinngemäss die fehlende Verwertbarkeit der Aussagen der Belastungszeuginnen aufgrund schwerer Verfahrensmängel (Beschwerde, S. 7).
2.2 Die erste Instanz stufte den Umstand, dass die Belastungszeuginnen nicht formell als Zeuginnen oder Auskunftspersonen einvernommen und entsprechend auf ihre Pflicht zu wahrheitsgemässen Aussagen sowie auf die Straffolgen des falschen Zeugnisses hingewiesen worden seien, nicht als Unverwertbarkeitsgrund ein (erstinstanzliches Urteil, S. 9). Die Vorinstanz lässt die Frage im Ergebnis offen und weist darauf hin, dass die erste Instanz die belastenden Aussagen lediglich auch als Indizien beigezogen habe. Diese stellten jedoch nicht das einzige Beweismaterial dar. Es stehe unbestrittenermassen fest, dass der Beschwerdeführer die von ihm gemieteten Wohnungen an die bei der polizeilichen Razzia vorgefundenen Frauen vermietet habe. Alle Frauen seien leicht und aufreizend bekleidet gewesen. Bei der Kontrolle der Zimmer seien Papierrollen, Kondome und Gleitcreme gefunden worden. Weitere Indizien ergäben sich aus dem Internet, wo sich auf «http//www.sexy-tipp.ch» die Kunden über die verschiedenen Prostituierten in der Bar austauschten (angefochtenes Urteil, S. 4).
Der Beschwerdeführer habe nicht nur gewusst, dass die Mieterinnen der Prostitution nachgegangen seien, sondern habe dies auch so gesteuert. Er sei zudem für den engen Konnex zwischen den für den Prostitutionsbetrieb vermieteten Zimmern sowie dem Barbetrieb verantwortlich gewesen und habe in der Bar "das Sagen" gehabt. Er habe denn auch selber ausdrücklich zugestanden, dass er die Bar betrieben und für den Barbetrieb verantwortlich gewesen sei. Der Inhalt seiner Aussagen werde durch die kontrollierten Frauen lediglich bestätigt und sei auch ohne diese hinreichend nachgewiesen (angefochtenes Urteil, S. 4 f.).
2.3 Gemäss § 50 aStPO/BS sind Zeuginnen und Zeugen vor der Einvernahme auf die Pflicht zur wahrheitsgemässen Aussage und auf das Recht zur Zeugnisverweigerung, falls dieses in Frage kommt, sowie auf die Straffolgen des falschen Zeugnisses hinzuweisen.
Ob die Unterlassung der Zeugenbelehrungen unter dem Geltungsbereich der StPO/BS zur Unverwertbarkeit der Aussagen führt, kann vorliegend offen gelassen werden. Entgegen der Ansicht des Beschwerdeführers stellt die Vorinstanz im Ergebnis nicht auf die Aussagen der Belastungszeuginnen ab. Sie begründet ausführlich, namentlich gestützt auf die Aussagen des Beschwerdeführers sowie auf die im Rahmen der koordinierten Polizeikontrolle am 17. Juli 2007 in der Bar sowie den vermieteten Wohnungen gewonnenen Indizien, weshalb der Beschwerdeführer Ausländerinnen ohne Arbeitsbewilligung in der Schweiz beschäftigt hat.
3. 3.1 Die Vorinstanz bestätigt die Verurteilung des Beschwerdeführers gestützt auf die per 1. Januar 2008 aufgehobenen Art. 23 Abs. 4 und 5 ANAG. Die übrigen erstinstanzlichen Schuldsprüche hob die Vorinstanz hingegen wegen unechter Konkurrenz auf und sprach den Beschwerdeführer frei.
3.2 Gemäss Art. 23 Abs. 4 ANAG wird mit einer Busse bis zu Fr. 5'000.-- für jeden rechtswidrig beschäftigten Ausländer, der nicht berechtigt ist, in der Schweiz zu arbeiten, bestraft. Handelt der Täter fahrlässig, so beträgt die Busse bis zu Fr. 3'000.--. In besonders leichten Fällen kann von einer Bestrafung Umgang genommen werden. Wenn der Täter aus Gewinnsucht handelt, ist der Richter an diese Höchstbeträge nicht gebunden.
Die qualifizierte Tatbegehung nach Abs. 5 derselben Bestimmung sieht vor, dass ein gemäss Abs. 4 wegen vorsätzlicher Begehung rechtskräftig Verurteilter zusätzlich zur Busse mit Geldstrafe bis zu 180 Tagessätzen bestraft werden kann, wenn er innert fünf Jahren erneut rechtswidrig einen Ausländer beschäftigt, was auf den Beschwerdeführer unbestrittenermassen zutrifft.
3.3 Nach Art. 117 Abs. 1 des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (Ausländergesetz, AuG) wird mit Freiheitsstrafe bis zu einem Jahr oder Geldstrafe bestraft, wer als Arbeitgeberin oder Arbeitgeber vorsätzlich Ausländerinnen und Ausländer beschäftigt, die in der Schweiz nicht zur Ausübung einer Erwerbstätigkeit berechtigt sind, oder wer eine grenzüberschreitende Dienstleistung in der Schweiz in Anspruch nimmt, für welche der Dienstleistungserbringer keine Bewilligung besitzt. In schweren Fällen ist die Strafe Freiheitsstrafe bis zu drei Jahren oder Geldstrafe. Mit der Freiheitsstrafe ist eine Geldstrafe zu verbinden.
Gemäss Art. 117 Abs. 2 AuG wird mit Freiheitsstrafe bis zu drei Jahren oder Geldstrafe bestraft, und mit der Freiheitsstrafe ist eine Geldstrafe zu verbinden, wer nach Abs. 1 rechtskräftig verurteilt wurde und innert fünf Jahren erneut Straftaten nach Abs. 1 begeht.
3.4 Die inkriminierten Handlungen des Beschwerdeführers fanden vor dem Inkrafttreten des AuG am 1. Januar 2008 statt. Art. 126 Abs. 4 AuG sieht hierbei vor, dass auf Widerhandlungen, die vor dem Inkrafttreten dieses Gesetzes begangen wurden, dessen Strafbestimmungen anzuwenden sind, sofern sie für den Täter milder sind. Weder die Vorinstanz noch die erste Instanz begründen, weshalb sie vorliegend die Strafbestimmungen des ANAG und nicht des AuG anwenden.
3.5 Ob das neue im Vergleich zum alten Gesetz milder ist, beurteilt sich nicht nach einer abstrakten Betrachtungsweise, sondern in Bezug auf den konkreten Fall (Grundsatz der konkreten Vergleichsmethode). Grundsätzlich müssen in erster Linie die rechtlichen Bedingungen der streitigen Straftat geprüft werden. Ist das Verhalten sowohl nach altem als auch nach neuem Recht strafbar, muss ein Vergleich der insgesamt zu gewärtigenden Sanktionen vorgenommen werden. Der Richter hat die Tat sowohl nach altem als auch nach neuem Recht (hypothetisch) zu prüfen und durch Vergleich der Ergebnisse festzustellen, nach welchem der beiden Rechte der Täter besser wegkommt. Eine entscheidende Rolle spielt die angedrohte Höchststrafe; massgeblich sind jedoch alle anwendbaren Strafzumessungsregeln (<ref-ruling> E. 2.2; mit Bezug auf den revidierten Allgemeinen Teil des Strafgesetzbuches 134 IV 82 E. 6.2.1; <ref-ruling> E. 2c; je mit Hinweisen).
Zu berücksichtigen ist, dass die Geldstrafe und die Busse insofern gleichwertig sind, als sie beide den Täter in seinem Vermögen treffen. Sie unterscheiden sich dagegen in der Berechnungsart, die je nach Fallkonstellation dazu führen kann, dass eine dieser Strafen für den Täter milder sein kann als die andere. Zudem kann für die Geldstrafe im Unterschied zur Busse teilweise oder vollumfänglich der bedingte Vollzug gewählt werden, weshalb sie diesfalls auch dann in ihren Auswirkungen milder erscheint, wenn ihr Maximalbetrag höher liegt als derjenige der Busse (<ref-ruling> E. 2.5 mit Hinweis).
Der Richter hat deshalb den Sachverhalt in umfassender Weise sowohl nach dem alten als auch nach dem neuen Recht zu beurteilen und die Ergebnisse miteinander zu vergleichen. Dies hat die Vorinstanz unterlassen. Sie sanktionierte den Beschwerdeführer einzig nach altem Recht mit einer bedingt vollziehbaren Geldstrafe von 120 Tagessätzen zu Fr. 80.-- sowie einer Busse von Fr. 29'500.--. Da dem Sachrichter bei der Strafzumessung nach konstanter bundesgerichtlicher Rechtsprechung (129 IV 6 E. 6.1; <ref-ruling> E. 4b; je mit Hinweisen) ein erheblicher Spielraum des Ermessens zusteht, kann das Bundesgericht nicht anstelle der Vorinstanz die Strafzumessung auch nach neuem Recht gestützt auf den Tatbestand von Art. 117 Abs. 2 AuG vornehmen und dann einen Vergleich ziehen.
Die Sache ist zur Bestimmung der lex mitior an die Vorinstanz zurückzuweisen. Bei dieser Sachlage ist auf die weiteren Vorbringen des Beschwerdeführers nicht einzugehen.
4. Die Beschwerde ist teilweise gutzuheissen. Das Urteil des Appellationsgerichts des Kantons Basel-Stadt vom 3. Dezember 2010 ist aufzuheben und die Sache an die Vorinstanz zurückzuweisen. Bei diesem Ausgang des Verfahrens hat der Beschwerdeführer reduzierte Gerichtskosten zu tragen. Dem Kanton Basel-Stadt sind keine Gerichtskosten aufzuerlegen (Art. 66 Abs. 1 i.V.m. Abs. 4 BGG). Der Kanton Basel-Stadt hat dem Beschwerdeführer eine reduzierte Parteientschädigung auszurichten (Art. 68 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen. Das Urteil Appellationsgerichts des Kantons Basel-Stadt vom 3. Dezember 2010 wird aufgehoben und die Sache an die Vorinstanz zurückgewiesen.
2. Die Gerichtskosten von Fr. 1'000.-- werden dem Beschwerdeführer auferlegt.
3. Der Kanton Basel-Stadt hat dem Beschwerdeführer eine Parteientschädigung von Fr. 1'500.-- auszurichten.
4. Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Ausschuss, schriftlich mitgeteilt.
Lausanne, 26. Juli 2011
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Der Gerichtsschreiber:
Wiprächtiger Keller