Sachverhalt: A. X._ stellte am 18. September 2012 in der Schweiz ein Asylgesuch, welches das damalige Bundesamt für Migration (BFM) mit Verfügung vom 7. November 2014 abwies. Die von X._ dagegen erhobene Beschwerde wies das Bundesverwaltungsgericht mit Urteil vom 19. Januar 2015 ab. Da X._ die Schweiz nach dem negativen Asylentscheid nicht verliess, verurteilte ihn die Staatsanwaltschaft Zürich-Limmat mit Strafbefehl vom 6. Juni 2016 wegen rechtswidrigen Aufenthalts zu einer bedingten Geldstrafe von 90 Tagessätzen zu Fr. 30.--, unter Ansetzung einer Probezeit von zwei Jahren. Am 30. Mai 2017 wurde X._erneut einer Polizeikontrolle unterzogen, woraufhin die Staatsanwaltschaft Winterthur/Unterland gegen ihn am 31. Mai 2017 einen weiteren Strafbefehl wegen rechtswidrigen Aufenthalts erliess. X._ erhob dagegen Einsprache. In der Folge sprach ihn das Bezirksgericht Dielsdorf am 22. Januar 2018 des rechtswidrigen Aufenthalts im Sinne von Art. 115 Abs. 1 lit. b AuG schuldig und verurteilte ihn zu einer unbedingten Geldstrafe von 120 Tagessätzen zu Fr. 10.--. Es verzichtete auf den Widerruf der mit Strafbefehl der Staatsanwaltschaft Zürich-Limmat vom 6. Juni 2016 bedingt ausgesprochenen Geldstrafe von 90 Tagessätzen und verlängerte stattdessen die Probezeit von zwei Jahren um ein Jahr. X._ und die Staatsanwaltschaft erhoben gegen dieses Urteil im Strafpunkt Berufung. Das Obergericht des Kantons Zürich stellte mit Urteil vom 14. September 2018 die Rechtskraft des erstinstanzlichen Schuldspruchs wegen rechtswidrigen Aufenthalts fest. Es bestrafte X._ mit einer unbedingten Freiheitsstrafe von vier Monaten und verzichtete in Bestätigung des erstinstanzlichen Urteils auf den Widerruf der am 6. Juni 2016 bedingt ausgesprochenen Vorstrafe. B. X._ beantragt mit Beschwerde in Strafsachen, das Urteil vom 14. September 2018 sei aufzuheben und er sei stattdessen mit einer angemessenen Geldstrafe von maximal 120 Tagessätzen zu Fr. 10.-- zu bestrafen, wobei ihm der bedingte Vollzug zu gewähren sei. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. X._ ersucht um unentgeltliche Rechtspflege. C. Das Obergericht und die Staatsanwaltschaft verzichteten auf eine Vernehmlassung.