Sachverhalt: A. Die Staatsanwaltschaft Winterthur wirft A._ vor, zwischen Dezember 2017 und April 2018 vier Mal ohne gültiges Visum und davon zudem drei Mal auch ohne gültigen Reisepass in die Schweiz eingereist zu sein und sich dort bis zu seiner Verhaftung insgesamt 146 Tage aufgehalten zu haben, obwohl er um die Notwendigkeit eines gültigen Aufenthaltstitels bzw. eines gültigen Reisepasses sowie einer Bewilligung für seine Einreise und den Aufenthalt in der Schweiz gewusst habe. Das Bezirksgericht verurteilte A._ am 7. August 2018 wegen mehrfacher rechtswidriger Einreise und mehrfachen rechtswidrigen Aufenthalts zu einer (unbedingten) Freiheitsstrafe von sechs Monaten unter Anrechnung von einem Tag Untersuchungshaft und auferlegte ihm die Kosten des Strafverfahrens. B. Auf Berufung von A._ verurteilte das Obergericht des Kantons Zürich ihn am 5. Februar 2019 ebenfalls wegen mehrfacher rechtswidriger Einreise und mehrfachen rechtswidrigen Aufenthalts und sprach eine unbedingte Freiheitsstrafe von fünf Monaten aus. Gleichzeitig auferlegte es ihm sämtliche Kosten des Berufungsverfahrens, mit Ausnahme derjenigen der amtlichen Verteidigung, unter Vorbehalt einer Rückzahlungspflicht von A._. C. A._ führt Beschwerde in Strafsachen und beantragt zusammengefasst, das Urteil des Obergerichts vom 5. Februar 2019 sei aufzuheben und das Strafverfahren gegen ihn einzustellen. Die Verfahrens- und Gerichtskosten seien auf die Staatskasse zu nehmen und ihm sei für zu Unrecht erlittene Haft eine Genugtuung in Höhe von Fr. 30'000.- zuzusprechen. Eventualiter sei die Sache zur Neubeurteilung an das Obergericht zurückzuweisen. A._ ersucht um unentgeltliche Rechtspflege. Das Obergericht und die Oberstaatsanwaltschaft des Kantons Zürich verzichten jeweils auf eine Vernehmlassung.