Sachverhalt:
A. X._ ist tunesischer Staatsangehöriger und reiste am 20. Januar 2003 in die Schweiz ein. Sein Asylgesuch wurde am 16. Mai 2003 vom Bundesamt für Flüchtlinge (heute Bundesamt für Migration) abgewiesen. Die dagegen bei der Schweizerischen Asylrekurskommission (heute Bundesverwaltungsgericht) erhobene Beschwerde blieb erfolglos.
Der Beschwerdeführer heiratete am 1. Juni 2004 die schweizerische Staatsangehörige Y._. In der Folge wurde ihm eine Aufenthaltsbewilligung zum Verbleib bei der Ehefrau erteilt. Am 11. Juni 2005 wurde der Beschwerdeführer Vater des ausserehelichen Kindes A._. Er anerkannte seinen Sohn am 20. Juni 2005. Die Ehe mit Y._ wurde am 19. Juni 2006 geschieden.
Das Bundesamt für Migration wies am 10. März 2008 das Gesuch des Beschwerdeführers um Verlängerung der Aufenthaltsbewilligung ab. Von Oktober bis Ende Dezember 2010 verbüsste er eine Bestrafung wegen rechtswidrigen Aufenthalts in der Schweiz. Das Migrationsamt des Kantons Zürich forderte den Beschwerdeführer am 24. Dezember 2010 auf, innerhalb von 48 Stunden nach seiner Entlassung aus dem Strafvollzug am 31. Dezember 2010 die Schweiz selbständig zu verlassen.
Noch während des Strafvollzugs reichte der Beschwerdeführer am 13. Dezember 2010 beim Zivilstandsamt der Stadt Zürich ein Gesuch um Vorbereitung der Eheschliessung mit der in der Schweiz niedergelassenen portugiesischen Staatsangehörigen Z._ ein. Am 1. Juni 2011 stellte er beim Migrationsamt des Kantons Zürich ein neues Gesuch um Erteilung der Aufenthaltsbewilligung, welche ihm schliesslich am 5. Dezember 2011 gewährt wurde.
B. Das Bezirksgericht Zürich sah es als erwiesen an, dass sich der Beschwerdeführer nach Ablauf der Ausreisefrist vom 3. Januar bis 30. Juni 2011 illegal in der Schweiz aufgehalten hatte. Es verurteilte ihn am 6. Juni 2012 wegen Widerhandlung gegen das Ausländergesetz zu 60 Tagen Freiheitsstrafe. Deren Vollzug schob es auf und setzte die Probezeit auf drei Jahre fest. Sowohl der Beschwerdeführer wie auch die Staatsanwaltschaft erhoben Berufung. Das Obergericht des Kantons Zürich bestätigte am 16. Oktober 2012 den erstinstanzlichen Schuldspruch und verurteilte den Beschwerdeführer zu einer unbedingten Geldstrafe von 60 Tagessätzen zu je Fr. 60.--.
C. X._ führt Beschwerde in Strafsachen. Er beantragt, das vorinstanzliche Urteil sei aufzuheben, und er sei vom Vorwurf der Widerhandlung gegen das Ausländergesetz freizusprechen.

Erwägungen:
1. 1.1 Der Beschwerdeführer macht geltend, seine Bestrafung wegen rechtswidrigen Aufenthalts widerspreche der Rechtsprechung des Gerichtshofs der Europäischen Union.
1. 1.1 Der Beschwerdeführer macht geltend, seine Bestrafung wegen rechtswidrigen Aufenthalts widerspreche der Rechtsprechung des Gerichtshofs der Europäischen Union.
1.2 Die Vorinstanz hat unter Hinweis auf die bundesgerichtliche Rechtsprechung diesen Einwand verworfen.
1.2 Die Vorinstanz hat unter Hinweis auf die bundesgerichtliche Rechtsprechung diesen Einwand verworfen.
1.3 Die EU-Rückführungsrichtlinie räumt dem verwaltungsrechtlichen Rückführungsverfahren den Vorrang vor strafrechtlichen Sanktionen ein. Hält sich ein Drittstaatsangehöriger widerrechtlich in einem Schengen-Staat auf, ist der betreffende Staat verpflichtet, die geeigneten Vorkehren für eine effektive Rückführung in die Wege zu leiten. Er soll sich nicht darauf beschränken können, mit einer Strafandrohung oder einer Bestrafung wegen rechtswidrigen Aufenthalts bloss indirekt Druck auf den Drittstaatsangehörigen auszuüben, damit dieser das Land unkontrolliert verlässt, sich aber weiterhin im Schengen-Raum aufhält. Nach den Intentionen der EU-Rückführungsrichtlinie soll dies vermieden und der Drittstaatsangehörige effektiv in sein Heimatland ausgeschafft werden.
1.4 Das Bundesgericht hat sich ausführlich mit der Anwendung der Richtlinie 2008/115/EG des Europäischen Parlaments und des Rates vom 16. Dezember 2008 über gemeinsame Normen und Verfahren in den Mitgliedstaaten zur Rückführung illegal aufhältiger Drittstaatsangehöriger (ABl. L 348 vom 24. Dezember 2008, S. 98 ff.; nachfolgend EU-Rückführungsrichtlinie) und dem Verhältnis zur innerstaatlichen Strafbarkeit des rechtswidrigen Aufenthalts befasst. Auf diese grundlegenden Ausführungen kann verwiesen werden (vgl. Urteil 6B_196/2012 vom 24. Januar 2013 E. 2). Das Bundesgericht hielt fest, dass nach der EU-Rückführungsrichtlinie nationale Strafbestimmungen dort nicht ausgeschlossen sind, wo im verwaltungsrechtlichen Verfahren alles für den Vollzug der Rückkehrentscheidung Zumutbare vorgekehrt worden ist, dieser indessen am Verhalten des Betroffenen scheitert (vgl. dazu auch Urteil 6B_188/2012 mit Hinweisen sowie Urteile 6B_617/2012 und 6B_618/2012). Eine Bestrafung wegen rechtswidrigen Aufenthalts kommt somit nur infrage, wenn die Ausreise objektiv möglich ist (Urteil 6B_482/2010 E. 3.2.2 und 3.2.3) und zuvor ein administratives Rückführungsverfahren in die Wege geleitet worden ist oder sich ein derartiges Verfahren von vornherein als undurchführbar erweist.
1.5 Die Vorinstanz räumt ein, dass gegen den Beschwerdeführer keine ausländerrechtlichen Zwangsmassnahmen angeordnet wurden (Urteil, S. 7) und begründete ihre Verurteilung allein damit, dass er von Anfang und mit aller Deutlichkeit erklärt habe, die Schweiz nicht verlassen zu wollen, obwohl ihm dies objektiv möglich gewesen wäre (Urteil, S. 8). Damit lässt sich der Schuldspruch unter Berücksichtigung der EU-Rückführungsrichtlinie nicht begründen. Den Akten, nicht aber dem angefochtenen Urteil, lässt sich jedoch entnehmen, dass der Beschwerdeführer ein erstes Mal bereits im Jahr 2001 zwangsweise ausgeschafft wurde und das Migrationsamt des Kantons Zürich bereits am 29. März 2009 gegenüber dem Beschwerdeführer eine Wegweisungsverfügung erliess und die Kantonspolizei Zürich mit dem Vollzug der Ausschaffung beauftragte (Akten Vorinstanz 22/20). Die Ausschaffung konnte nicht vollzogen werden, weil der Beschwerdeführer in der Zwischenzeit untergetaucht war und erst am 30. Juni 2011 festgenommen werden konnte (Akten Vorinstanz 22/2). Das Migrationsamt hatte somit im verwaltungsrechtlichen Verfahren alles für den Vollzug der Rückführung Zumutbare vorgekehrt. Die Rückführung war indessen am Verhalten des Beschwerdeführers gescheitert. Seine Bestrafung wegen rechtswidrigen Aufenthalts erweist sich auch unter Mitberücksichtigung der EU-Rückführungsrichtlinie als bundesrechtskonform. Die Beschwerde ist abzuweisen.
2. Bei diesem Ausgang des Verfahrens sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (<ref-law>). Das Gesuch um unentgeltliche Rechtspflege ist in Anwendung von <ref-law> abzuweisen, weil die Rechtsbegehren aussichtslos erschienen. Der finanziellen Lage des Beschwerdeführers ist bei der Bemessung der Gerichtskosten Rechnung zu tragen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 800.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Strafkammer, schriftlich mitgeteilt.
Lausanne, 19. April 2013
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Der Gerichtsschreiber: Keller