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. 