Sachverhalt: A. Das Staatssekretariat für Migration erteilte X._, geb. A._, am 6. Februar 2015 ein Einreiseverbot für den Zeitraum vom 11. Februar 2015 bis zum 10. Februar 2020, lautend auf ihren damaligen Familiennamen B._. X._ stellte am 16. August 2016 ein Gesuch um Erteilung eines Visums für einen langfristigen Aufenthalt in der Schweiz zwecks Verbleib bei ihrem Ehegatten (Familiennachzug). Auf dem Antragsformular gab sie bei der Frage nach "bisherigen Aufenthalten in der Schweiz" als Antwort "Nein" an. Die Schweizer Behörden erteilten X._ am 19. Oktober 2016 ein Visum mit Gültigkeit bis zum 3. Januar 2017. Damit reiste X._ am 23. Oktober 2016 in die Schweiz ein. Bei der Anmeldung auf der Einwohnerkontrolle U._ wurde sie verhaftet. B. Das Bezirksgericht Bülach sprach X._ am 19. Dezember 2016 vom Vorwurf der Widerhandlungen gegen das Ausländergesetz (AuG; SR 142.20) frei. Auf Berufung der Staatsanwaltschaft verurteilte das Obergericht des Kantons Zürich X._ am 23. Mai 2018 wegen Täuschung der Behörden (Art. 118 Abs. 1 AuG), rechtswidriger Einreise (Art. 115 Abs. 1 lit. a AuG) sowie rechtswidrigen Aufenthalts (Art. 115 Abs. 1 lit. b AuG) zu einer vollziehbaren Freiheitsstrafe von sechs Monaten. Das beschlagnahmte Bargeld von Fr. 1'000. - zog es zur teilweisen Deckung der Verfahrenskosten ein und auferlegte X._ die erst- und zweitinstanzlichen Verfahrenskosten. C. Gegen dieses Urteil erhebt X._ Beschwerde in Strafsachen. Sie beantragt, das Urteil des Obergerichts des Kantons Zürich vom 23. Mai 2018 sei aufzuheben und sie sei vollumfänglich freizusprechen. Eventualiter sei das Urteil aufzuheben und die Sache zur neuen Entscheidung an die Vorinstanz zurückzuweisen. Gleichzeitig ersucht X._ um unentgeltliche Rechtspflege und Verbeiständung. D. Das Obergericht und die Oberstaatsanwaltschaft des Kantons Zürich haben auf eine Vernehmlassung verzichtet.