Sachverhalt:
A. X._ beschäftigte zwischen dem 15. August 2008 und dem 15. Juni 2009 die malaysische Staatsangehörige Y._ als Putzfrau in seiner Wohnung in der Stadt Zürich, nachdem er ihre Visitenkarte durch eine Drittperson erhalten hatte. Y._ reinigte in dieser Zeitspanne die Wohnung in der Regel alle zwei Wochen, insgesamt mindestens 16 Mal. X._ verzichtete darauf, von ihr die Bewilligung zur selbständigen oder unselbständigen Erwerbstätigkeit oder einen anderen Ausweis zu verlangen bzw. sich bei den zuständigen Behörden darüber zu erkundigen.
B. Das Bezirksgericht Zürich verurteilte X._ wegen Widerhandlung gegen das Ausländergesetz (stundenweise Beschäftigung von Y._ als Putzfrau ohne Arbeitsbewilligung) zu einer Geldstrafe von 60 Tagessätzen zu Fr. 230.--, bedingt aufgeschoben bei einer Probezeit von zwei Jahren, und zu einer Busse von Fr. 1'000.--.
Die von X._ dagegen erhobene Berufung wies das Obergericht des Kantons Zürich am 2. Februar 2012 ab.
C. X._ erhebt Beschwerde in Strafsachen. Er beantragt, das Urteil des Obergerichts sei aufzuheben. Er sei vom Vorwurf der vorsätzlichen Widerhandlung gegen das Ausländergesetz freizusprechen. Ausserdem sei ihm Schadenersatz für die Anwaltskosten und eine angemessene Entschädigung für die entstandenen Umtriebe zu entrichten.
D. Das Obergericht und die Staatsanwaltschaft des Kantons Zürich verzichten auf eine Vernehmlassung.

Erwägungen:
1. 1.1 Der Beschwerdeführer rügt eine unrichtige Sachverhaltsfeststellung der Vorinstanz. Er macht geltend, dass er seine Putzfrau beim ersten und einzigen Treffen im August 2008 gefragt habe, ob sie noch in weiteren Haushalten tätig sei und ob er sie noch bei der AHV anmelden müsse. Sie habe ihm geantwortet, sie arbeite bei mindestens 15 weiteren Kunden und sei bei der AHV als selbständig Erwerbende registriert.
Die Schlussfolgerung der Vorinstanz, eine asiatisch aussehende Person könne offensichtlich nicht aus dem Schengenraum stammen, weshalb er betreffend Arbeitsbewilligung hätte sensibilisiert sein sollen, sei nicht nur fragwürdig, sondern bedenklich. Es könne als allgemein bekannt vorausgesetzt werden, dass aufgrund des Aussehens keine Rückschlüsse auf die Staatsangehörigkeit getroffen werden könnten. Zudem dürfe die Vorinstanz nicht allgemein und losgelöst vom vorliegenden Fall argumentieren, die Problematik der Schwarzarbeit werde in der Bevölkerung breit diskutiert. Es obliege der Vorinstanz vielmehr, ihm konkret nachzuweisen, dass er begründete Zweifel am Vorliegen einer gültigen Arbeitsbewilligung hätte haben müssen. Die Putzfrau habe seit über drei Jahren in der Schweiz gelebt und gearbeitet, weshalb er keinen Anlass gehabt habe, an ihrem rechtmässigen Aufenthalt zu zweifeln. Er sei aufgrund der konkreten Umstände schlechterdings nicht auf die Idee gekommen, ihre Arbeits- und Aufenthaltsbewilligung einzusehen. Die Vorinstanz argumentiere widersprüchlich, indem sie sich auf seine Aussage berufe, er sei sich der Bewilligungsproblematik nicht bewusst gewesen, gleichzeitig aber ausführe, er habe die Notwendigkeit einer Arbeitsbewilligung gekannt und habe lediglich auf deren Vorhandensein vertraut. Die Vorinstanz habe auch nicht berücksichtigt, dass er von einer selbständigen Erwerbstätigkeit der Putzfrau ausgegangen sei. Als er sich mit seiner Putzfrau getroffen habe, hätten sich keine Hinweise auf eine fehlende Arbeitsbewilligung gezeigt (Beschwerde, S. 24-28).
1.2 Die Vorinstanz erwägt, der Beschwerdeführer habe - im Gegensatz zu seinem Verteidiger - ausgeführt, er sei davon ausgegangen, dass die Putzfrau Thailänderin sei. Es sei unglaubhaft, dass er während der ganzen Zeit der Anstellung seiner Putzfrau nie an die Notwendigkeit ihrer Arbeits- und Aufenthaltsbewilligung gedacht habe. Das Wissen um die Thematik der Schwarzarbeit sei in der Bevölkerung weit verbreitet und könne vom Beschwerdeführer, der Studien in Wirtschaftswissenschaften und Jurisprudenz abgeschlossen habe, vorausgesetzt werden. Die Änderung der Arbeitsbewilligungspflicht gewisser EU-Staatsangehöriger habe die Situation zwar unübersichtlicher gemacht. Ein Irrtum bezüglich Thailänderinnen oder Malaysierinnen sei jedoch lebensfremd (Urteil, S. 12 f.).
Der Beschwerdeführer mache widersprüchliche Aussagen. So habe er geltend gemacht, er sei sich des Bewilligungsproblems nicht bewusst gewesen, berufe sich aber gleichzeitig auf die rechtliche Natur des Anstellungsverhältnisses. Er könne vernünftigerweise nicht behaupten, von einem Auftragsverhältnis ausgegangen zu sein, wenn er seine Putzfrau gleichzeitig gefragt habe, ob er sie bei der AHV und der Unfallversicherung anmelden solle. In diesem Moment habe er zumindest kurz an die Thematik der Arbeitsbewilligung für Ausländer denken müssen (Urteil, S. 13 f.).
1.3 Das Bundesgericht legt seinem Urteil den Sachverhalt zu Grunde, den die Vorinstanz festgestellt hat (<ref-law>). Die vorinstanzliche Sachverhaltsfeststellung kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>; <ref-law>). Offensichtlich unrichtig im Sinne von <ref-law> ist die Sachverhaltsfeststellung, wenn sie willkürlich ist (<ref-ruling> E. 4.2 mit Hinweisen; zum Begriff der Willkür <ref-ruling> E. 7.1; <ref-ruling> E. 4.2; je mit Hinweisen). Eine entsprechende Rüge muss klar und substantiiert begründet werden (Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG; <ref-ruling> E. 4.2.3; <ref-ruling> E. 1.3.1; je mit Hinweisen). Der Beschwerdeführer, der die Sachverhaltsfeststellung der Vorinstanz anfechten will, muss mithin detailliert aufzeigen, inwiefern die gerügten Feststellungen bzw. die Unterlassung von Feststellungen offensichtlich unrichtig sind oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen. In der Beschwerde muss im Einzelnen dargelegt werden, inwiefern der angefochtene Entscheid an einem qualifizierten und offensichtlichen Mangel leidet. Auf eine rein appellatorische Kritik tritt das Bundesgericht nicht ein (<ref-ruling> E. 4.2.3; <ref-ruling> E. 2.8; je mit Hinweisen).
1.4 Der Beschwerdeführer vermag keine Willkür an der vorinstanzlichen Sachverhaltsfeststellung darzutun. Da er selber angenommen hat, dass die Putzfrau aus Thailand stammt, zielt seine Kritik an den vorinstanzlichen Feststellungen zu deren Herkunft ins Leere. Die Vorinstanz verfällt auch nicht in Willkür, wenn sie dem Beschwerdeführer unterstellt, sich der Problematik der Schwarzarbeit bewusst gewesen zu sein. Nicht zu beanstanden ist ferner ihre Feststellung, der Beschwerdeführer argumentiere widersprüchlich, indem er einerseits nicht an das Bewilligungsproblem gedacht haben will, sich andererseits aber auf die rechtliche Natur des Anstellungsverhältnisses beruft.
2.1 2.1.1 Nach Auffassung des Beschwerdeführers verletzt die Vorinstanz Bundesrecht, indem sie Art. 117 des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (Ausländergesetz, AuG; SR 142.20) unrichtig anwende. Er rügt zudem eine Verletzung des Legalitätsprinzips (<ref-law>) sowie des Bestimmtheits- und Klarheitsgebots (<ref-law>).
Es sei unbestritten, dass seine Putzfrau in selbständiger Erwerbstätigkeit für ihn tätig war. Die Vorinstanz vertrete die Meinung, der ausländerrechtliche Arbeitgeberbegriff sei so auszulegen, dass auch ein Auftraggeber, der sich von einem Selbständigerwerbenden die ihm übertragenen Geschäfte oder Dienste besorgen lasse, als Arbeitgeber zu qualifizieren sei. Diese Auffassung verstosse gegen die Praxis des Bundesgerichts, insbesondere gegen <ref-ruling>, wonach ein Auftraggeber, der selbständig Erwerbende beschäftige, nicht unter den Arbeitgeberbegriff subsumiert werden könne. Das Bundesgericht habe diese Rechtsprechung in mehreren Entscheiden (zuletzt in <ref-ruling>59) bestätigt. Gemäss Literatur machten sich nur die Empfänger von hier nicht zutreffenden grenzüberschreitenden Dienstleistungen gemäss Art. 117 Abs. 1 2. Halbsatz AuG strafbar. In der Botschaft zum Bundesgesetz über die Ausländerinnen und Ausländer vom 8. März 2002 (BBl 2002, S. 3709 ff.) werde bewusst zwischen Arbeitgebern und Empfängern von Dienstleistungen unterschieden. Es bleibe kein Raum, ein Auftragsverhältnis unter die erste Tatbestandsvariante zu subsumieren (Beschwerde, S. 6-15).
2.1.2 Der Beschwerdeführer argumentiert, selbst wenn der objektive Tatbestand bejaht werde, bestünden in subjektiver Hinsicht insgesamt erhebliche und unüberwindbare Zweifel an einer eventualvorsätzlichen Tatbegehung, die sich mit vernünftigen Argumenten nicht beseitigen liessen. Zudem sei bei ihm kein Motiv erkennbar, sich wegen illegaler Beschäftigung einer Putzfrau dem Risiko einer strafrechtlichen Verurteilung auszusetzen (Beschwerde, S. 27).
2.1.3 Der Beschwerdeführer rügt ausserdem eine unrichtige Anwendung und Auslegung von Art. 91 AuG (Sorgfaltspflicht von Arbeitgebern und Dienstleistungsempfängern), da die Vorinstanz eine unzulässige Qualifikation als Arbeitgeber vornehme (Beschwerde, S. 15 f.). Er macht in den weiteren Teilen seiner Beschwerde Verletzungen des rechtlichen Gehörs, der Begründungspflicht, der Unschuldsvermutung bzw. des Grundsatzes "in dubio pro reo" geltend (Beschwerde, S. 17-24).
2.1.4 Schliesslich beruft sich der Beschwerdeführer auf Rechtsirrtum. Die Putzfrau sei mittels Strafbefehls wegen Ausübung einer selbständigen Erwerbstätigkeit ohne Bewilligung verurteilt worden. Ebenso gehe die Vorinstanz bei ihr ebenfalls von einer selbständigen Erwerbstätigkeit aus. Er sei daher in zivilrechtlicher Hinsicht Auftraggeber in einem Auftragsverhältnis. Gleichzeitig sei er gemäss Vorinstanz Arbeitgeber einer selbständig erwerbenden Person. Dieses Rechtsverständnis sei nicht nachvollziehbar und widerspreche dem Gesetzestext. Sollte diese Rechtsauffassung in objektiver Hinsicht dennoch gestützt werden, sei in subjektiver Hinsicht von einem wesentlichen Subsumtionsirrtum auszugehen (Beschwerde, S. 29 f.).
2.2 Die Vorinstanz erwägt, das Bundesgericht verstehe den Arbeitgeberbegriff - wie schon unter dem Geltungsbereich des früheren Rechts - weit. Diese Auffassung werde auch in der Literatur und den Materialien vertreten. Art. 117 AuG sei nicht auf Arbeitsverträge im Sinne des Obligationenrechts beschränkt. Arbeitgeber sei vielmehr, wer jemanden für sich eine Erwerbstätigkeit nach Art. 11 Abs. 2 AuG ausüben lasse. Entsprechend unterstehe der Beschwerdeführer der Prüfungspflicht nach Art. 91 AuG und habe sich zu vergewissern, dass eine Berechtigung zur Erwerbstätigkeit bestehe (Urteil, S. 5 ff.). Die Vorinstanz bejaht neben dem objektiven auch den subjektiven Tatbestand. Der Beschwerdeführer habe bewusst auf die Vorlage einer Arbeitsbewilligung verzichtet. Es sei ihm zwar kein direkter Vorsatz zu unterstellen. Es sei davon auszugehen, dass er die Möglichkeit der fehlenden Bewilligung als möglich erachtet und das entsprechende Risiko im Sinne von Eventualvorsatz bewusst in Kauf genommen habe. Eine fahrlässige Tatbegehung sei auszuschliessen (Urteil, S. 14).
2.3 Gemäss Art. 117 Abs. 1 AuG wird 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 (1. Halbsatz). Ebenfalls wird bestraft, wer eine grenzüberschreitende Dienstleistung in der Schweiz in Anspruch nimmt, für welche der Dienstleistungserbringer keine Bewilligung besitzt (2. Halbsatz). Nach Art. 91 AuG hat sich der Arbeitgeber vor dem Stellenantritt der Ausländerin oder des Ausländers durch Einsicht in den Ausweis oder durch Nachfrage bei den zuständigen Behörden zu vergewissern, dass die Berechtigung zur Erwerbstätigkeit in der Schweiz besteht (Abs. 1). Wer eine grenzüberschreitende Dienstleistung in Anspruch nimmt, hat sich durch Einsicht in den Ausweis oder durch Nachfrage bei den zuständigen Behörden zu vergewissern, dass die Person, welche die Dienstleistung erbringt, zur Ausübung der Erwerbstätigkeit in der Schweiz berechtigt ist (Abs. 2).
2.4 Die Rügen des Beschwerdeführers sind unbegründet. Die Vorinstanz qualifiziert zwar die Arbeitstätigkeit der Putzfrau ohne weitere Begründung als selbständige Erwerbstätigkeit (Urteil, S. 8). Die Staatsanwaltschaft Zürich-Limmat büsste die Putzfrau ausserdem wegen Ausübung einer selbständigen Erwerbstätigkeit ohne Bewilligung. Gemäss Lehre und Rechtsprechung ist der Arbeitgeberbegriff im Ausländerrecht, wie schon unter dem Geltungsbereich des aufgehobenen Art. 23 Abs. 4 aANAG (siehe dazu <ref-ruling> E. 4.1), weit zu verstehen. Das Bundesgericht hielt fest, dass sich diese Bestimmung nicht auf Arbeitgeber im zivilrechtlichen Sinne (<ref-law>) beschränkte. "Beschäftigen" bedeutete vielmehr, jemanden gegen Entgelt eine Erwerbstätigkeit ausüben zu lassen, wobei es auf die Natur des Rechtsverhältnisses nicht ankam (vgl. schon <ref-ruling>).
Obwohl der Gesetzgeber die Nachfolgebestimmung in Art. 117 Abs. 1 AuG in seiner deutschen und italienischen Fassung neu formuliert hat ("Wer als Arbeitgeberin oder Arbeitgeber vorsätzlich Ausländerinnen und Ausländer beschäftigt..." bzw. "Chiunque, in qualità di datore di lavoro, impiega intenzionalmente stranieri..."), weist sie gegenüber Art. 23 Abs. 4 aANAG, welcher den Arbeitgeberbegriff nicht verwendete, keine andere Tragweite auf (vgl. <ref-ruling>53 E. 1.5 und 135 IV 159 E. 1.4; je mit Hinweisen). Die französische Fassung von Art. 117 Abs. 1 AuG spricht denn auch weiterhin nur von "Quiconque, intentionnellement, emploie un étranger...". Für die Annahme eines Irrtums über die Rechtswidrigkeit (<ref-law>) verbleibt unter diesen Umständen kein Raum.
2.5 Der Beschwerdeführer wendet sich auch zu Unrecht gegen den Vorwurf des Eventualvorsatzes. Die Vorinstanz verneint einen direkten Vorsatz, geht aber davon aus, dass er die Möglichkeit der fehlenden Bewilligungen aufgrund der Umstände und seines Wissens als möglich erachtet haben musste. Entsprechend hat er das Risiko im Sinne des Eventualvorsatzes bewusst in Kauf genommen (zum Begriff des Eventualvorsatzes <ref-ruling> E. 4.2.3; vgl. auch <ref-ruling> E. 3.2.1 und 3.2.2). Dass beim Beschwerdeführer eigenen Angaben zufolge kein Motiv ersichtlich ist, sich dem Risiko einer strafrechtlichen Verurteilung auszusetzen (Beschwerde, S. 27), kann daran nichts ändern.
Die Vorinstanz verletzt kein Bundesrecht, indem sie den Beschwerdeführer als Arbeitgeber im Sinn von Art. 117 Abs. 1 AuG einstuft und ihn wegen Widerhandlung gegen das Ausländergesetz verurteilt.
3. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens werden die Gerichtskosten dem Beschwerdeführer auferlegt (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, I. Strafkammer, schriftlich mitgeteilt.
Lausanne, 12. November 2012
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Der Gerichtsschreiber: Keller