Sachverhalt:
A. Der jamaikanische Staatsangehörige X._ wurde durch das Migrationsamt der Sicherheitsdirektion des Kantons Zürich mit Wegweisungsverfügungen vom 3. April und 9. August 2009 aufgefordert, die Schweiz innert zwei Tagen zu verlassen. Dieser Aufforderung kam er nicht nach.
B. Das Bezirksgericht Zürich sprach X._ mit Entscheid vom 11. Dezember 2009 vom Vorwurf der mehrfachen Widerhandlung gegen das Bundesgesetz über die Ausländerinnen und Ausländer frei.
C. Das Obergericht des Kantons Zürich sprach X._ mit Urteil vom 16. November 2010 des mehrfachen Vergehens gegen das Bundesgesetz über die Ausländerinnen und Ausländer schuldig. Es verurteilte ihn unter Anrechnung der erstandenen Untersuchungshaft von vier Tagen zu einer Freiheitsstrafe von fünf Monaten, als Zusatzstrafe zu der mit Urteil des Obergerichts des Kantons Zürich vom 15. Oktober 2009 ausgesprochenen Geldstrafe von 90 Tagessätzen zu Fr. 30.--.
D. Gegen dieses Urteil erhebt X._ Beschwerde in Strafsachen. Er beantragt, das Urteil des Obergerichts des Kantons Zürich vom 16. November 2010 sei aufzuheben und die Sache zur Neubeurteilung an das Obergericht zurückzuweisen. Eventualiter sei die Angelegenheit vom angerufenen Gericht zu beurteilen. Zudem beantragt er sinngemäss, ihm sei die unentgeltliche Prozessführung zu gewähren und Rechtsanwalt Guido Hensch als unentgeltlicher Rechtsvertreter beizuordnen.
E. Das Obergericht des Kantons Zürich sowie die Oberstaatsanwaltschaft des Kantons Zürich verzichten auf Vernehmlassungen.

Erwägungen:
1. Die Vorinstanz geht von folgendem Sachverhalt aus:
Der Beschwerdeführer reiste am 6. Mai 2006 legal in die Schweiz ein und stellte nach drei Monaten ein Gesuch um Erteilung der Aufenthaltsbewilligung. Dieses wurde in der Folge als gegenstandslos abgeschrieben, da der Beschwerdeführer nicht mehr auffindbar war. Eine Aufenthaltsbewilligung wurde ihm hiernach nie erteilt. Am 15. Juni sowie am 5. November 2007 verfügte das Migrationsamt des Kantons Zürich erstmals seine Wegweisung. Im Januar 2008 beabsichtigte das Bundesamt für Migration, bei der jamaikanischen Botschaft in Genf die Ausstellung eines Laisser-passer zu beantragen. Der Beschwerdeführer weigerte sich jedoch, das hierfür erforderliche Formular auszufüllen. Eine auf den 21. Februar 2008 geplante Rückführung nach Jamaika verweigerte er. Er machte geltend, nach England ausreisen zu wollen, da er einen zweiten Reisepass mit einem Visum für England besitze. Diesen Pass stellte er den Behörden indessen nie zu. Am 12. Juni 2008 verweigerte er erneut die Rückführung nach Jamaika. Das jamaikanische Konsulat bat am 7. August 2008 um Zustellung seines Reisepasses. Gemäss Auskunft des Bundesamtes für Migration befand sich der Pass am 26. September 2010 nach wie vor bei den jamaikanischen Behörden. Nach weiteren Wegweisungsverfügungen, denen der Beschwerdeführer nicht nachgekommen ist, bemühten sich die zuständigen Behörden um einen Daktyvergleich mit England im Hinblick auf seine allfällige Ausreise dorthin. Er verweigerte jedoch abermals die Abgabe einer schriftlichen Einwilligungserklärung. Hierauf ergingen die der vorinstanzlichen Verurteilung zu Grunde liegenden Wegweisungsverfügungen vom 3. April und 9. August 2009. Am 21. Juli 2009 stellte der Beschwerdeführer ein Gesuch um Erteilung der Aufenthaltsbewilligung für sich und seine englische Ehefrau, mit der er ein gemeinsames Kind hat. Dieses Gesuch war zum Zeitpunkt seiner Verhaftung am 16. September 2009 noch nicht beurteilt worden. Derweil scheint der Familiennachzug nicht mehr beabsichtigt zu sein, da der Beschwerdeführer sich scheiden lassen und seine Schweizer Freundin heiraten will.
Nach Auffassung der Vorinstanz hat sich der Beschwerdeführer vom 6. April bis zum 7. August 2009 und vom 11. August bis zum 16. September 2009 illegal in der Schweiz aufgehalten.
2. 2.1 Der Beschwerdeführer rügt, die Vorinstanz habe zu Unrecht ausschliesslich das Bundesgesetz über die Ausländerinnen und Ausländer angewendet. Er sei mit einer englischen Staatsangehörigen verheiratet, weshalb das Freizügigkeitsabkommen zur Anwendung gelange.
2. 2.1 Der Beschwerdeführer rügt, die Vorinstanz habe zu Unrecht ausschliesslich das Bundesgesetz über die Ausländerinnen und Ausländer angewendet. Er sei mit einer englischen Staatsangehörigen verheiratet, weshalb das Freizügigkeitsabkommen zur Anwendung gelange.
2.2 2.2.1 Das Bundesgesetz vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20) gilt, soweit keine anderen Bestimmungen des Bundesrechts oder von der Schweiz abgeschlossene völkerrechtliche Verträge zur Anwendung kommen. Für Staatsangehörige der Mitgliedstaaten der Europäischen Gemeinschaft (EG), ihre Familienangehörigen sowie für in die Schweiz entsandte Arbeitnehmerinnen und Arbeitnehmer von Arbeitgebern, die in einem dieser Staaten Wohnsitz oder Sitz haben, gilt dieses Gesetz nur so weit, als das Abkommen vom 21. Juni 1999 zwischen der Schweizerischen Eidgenossenschaft einerseits und der Europäischen Gemeinschaft und ihren Mitgliedstaaten andererseits über die Freizügigkeit keine abweichenden Bestimmungen enthält oder dieses Gesetz günstigere Bestimmungen vorsieht (Art. 2 Abs. 1 und 2 AuG). Das Freizügigkeitsabkommen (FZA; SR 0.142.112.681) bestimmt, dass Familienangehörige einer Person, die Staatsangehörige einer Vertragspartei ist und ein Aufenthaltsrecht hat, das Recht haben, bei ihr Wohnung zu nehmen (Art. 3 Abs. 1 Anhang I FZA).
2.2.2 Die Vorinstanz erwägt zu Recht, dem Beschwerdeführer komme gestützt auf das Freizügigkeitsabkommen kein Recht auf Aufenthalt in der Schweiz zu. Wie sich aus dem unbestrittenen Sachverhalt ergibt, hat seine Ehefrau in der Zeit vom 6. April bis zum 16. September 2009 nicht über eine Wohnung in der Schweiz verfügt, in welcher sie zusammen mit dem Beschwerdeführer gewohnt hat. Vielmehr arbeitete sie gemäss seinen Aussagen bis mindestens im Dezember 2009 im einem Kleidergeschäft in England (vorinstanzliches Urteil, E. II.5 S. 7 ff.). Somit gelangt das Bundesgesetzes über die Ausländerinnen und Ausländer zur Anwendung, wie die Vorinstanz zu Recht feststellt.
3. 3.1 Der Beschwerdeführer macht weiter geltend, er könne sich auf den Rechtfertigungsgrund des Notstands im Sinne von Art. 17 oder Art. 18 StGB berufen. Dadurch, dass ihm von Seiten der Behörden der Reisepass abgenommen und bis anhin nicht zurückgegeben worden sei, sei es ihm nicht möglich gewesen, die Schweiz zu verlassen.
3. 3.1 Der Beschwerdeführer macht weiter geltend, er könne sich auf den Rechtfertigungsgrund des Notstands im Sinne von Art. 17 oder Art. 18 StGB berufen. Dadurch, dass ihm von Seiten der Behörden der Reisepass abgenommen und bis anhin nicht zurückgegeben worden sei, sei es ihm nicht möglich gewesen, die Schweiz zu verlassen.
3.2 3.2.1 Gemäss Art. 115 Abs. 1 lit. b AuG wird mit Freiheitsstrafe bis zu einem Jahr oder Geldstrafe bestraft, wer sich rechtswidrig, namentlich nach Ablauf des bewilligungsfreien oder des bewilligten Aufenthalts, in der Schweiz aufhält.
Das Vorliegen des objektiven und subjektiven Tatbestands ist - abgesehen von der unter E. 2 behandelten Rüge - unbestritten. Diesbezüglich kann auf die zutreffenden Ausführungen der Vorinstanz verwiesen werden (vorinstanzliches Urteil, E. II.5 S. 5 ff.).

3.2.2 Soweit sich der Beschwerdeführer darauf beruft, sein tatbestandmässiges Handeln sei gerechtfertigt gewesen, ist in Übereinstimmung mit der Vorinstanz Art. 83 AuG zu berücksichtigen. Demnach verfügt das Bundesamt für Migration die vorläufige Aufnahme, wenn der Vollzug der Weg- oder Ausweisung nicht möglich ist (Abs. 1). Nicht möglich ist der Vollzug, wenn der Ausländer weder in den Heimat- oder in den Herkunftsstaat noch in einen Drittstaat ausreisen oder dorthin gebracht werden kann (Abs. 2). Jedoch wird die vorläufige Aufnahme nach dem Absatz 2 nicht verfügt, wenn die weg- oder ausgewiesene Person die Unmöglichkeit des Vollzugs der Weg- oder Ausweisung durch ihr eigenes Verhalten verursacht hat (Abs. 7 lit. c). Die Vorinstanz erwägt zu Recht, eine Ausreise des Beschwerdeführers nach Jamaika oder England wäre auch ohne Reisepass mit einem Laisser-passer oder einem englischen Visum möglich gewesen. Jedoch sei dieser seiner Mitwirkungspflicht nicht nachgekommen, indem er sich geweigert habe, das für das Laisser-passer notwendige Formular auszufüllen, den Behörden seinen vermeintlichen zweiten Pass mit einem Visum für England zuzustellen und die Einwilligungserklärung für den Daktyvergleich mit England zu unterzeichnen. Daher habe er durch sein Verhalten die Unmöglichkeit des Vollzugs der Wegweisung mitverschuldet. Eine vorläufige Aufnahme des Beschwerdeführers wurde demnach zu Recht nicht verfügt. Inwiefern sich der Beschwerdeführer darüber hinaus auf einen Rechtfertigungsgrund stützen könnte, ist nicht ersichtlich. Diesbezüglich verletzt das vorinstanzliche Urteil kein Bundesrecht.
4. 4.1 Sodann bringt der Beschwerdeführer vor, die ausgesprochene Freiheitsstrafe von fünf Monaten als Zusatzstrafe zu der mit Urteil des Obergerichts des Kantons Zürich vom 15. Oktober 2009 ausgesprochenen Geldstrafe sei nicht angemessen.
4. 4.1 Sodann bringt der Beschwerdeführer vor, die ausgesprochene Freiheitsstrafe von fünf Monaten als Zusatzstrafe zu der mit Urteil des Obergerichts des Kantons Zürich vom 15. Oktober 2009 ausgesprochenen Geldstrafe sei nicht angemessen.
4.2 4.2.1 Der Beschwerdeführer begründet nicht, inwiefern er die vorinstanzliche Strafzumessung als unangemessen erachtet. Die Vorinstanz würdigt die verschiedenen Strafzumessungsfaktoren ausführlich. Weder überschreitet sie noch missbraucht sie dabei ihr Ermessen.
4.2.2 Hingegen ist die vorinstanzliche Strafzumessung in anderer Hinsicht zu beanstanden. Das Obergericht des Kantons Zürich verurteilte den Beschwerdeführer am 15. Oktober 2009 wegen mehrfachen Vergehens und Übertretens des Betäubungsmittelgesetzes zu einer Geldstrafe von 90 Tagessätzen zu Fr. 30.--. Die Vorinstanz sprach eine Zusatzstrafe zu dieser Strafe aus, da der Beschwerdeführer die zu beurteilenden Straftaten vor dem Urteil des Obergerichts des Kantons Zürich vom 15. Oktober 2009 begangen hat. Damit stellt sich die Frage der Strafzumessung bei retrospektiver Konkurrenz nach <ref-law>.
Gemäss <ref-law> bestimmt das Gericht, wenn es eine Tat zu beurteilen hat, die der Täter beging, bevor er wegen einer anderen Tat verurteilt wurde, die Zusatzstrafe in der Weise, dass der Täter nicht schwerer bestraft wird, als wenn die strafbaren Handlungen gleichzeitig beurteilt worden wären. Somit soll das Asperationsprinzip auch bei retrospektiver Konkurrenz gewährleistet werden. Der Täter soll durch die getrennte Beurteilung von Straftaten, über die zeitlich zusammen hätte befunden werden können, nicht benachteiligt und soweit als möglich auch nicht besser gestellt werden. Die Zusatzstrafe gleicht dementsprechend die Differenz zwischen der ersten Einsatz- oder Grundstrafe und der hypothetischen Gesamtstrafe aus, die nach Auffassung des Richters bei Kenntnis der später beurteilten Straftat ausgefällt worden wäre (BGE 6B_460/2010 vom 4. Februar 2011 E. 2.2 mit Hinweis).
4.2.3 Zunächst versäumt es die Vorinstanz, bei der Bildung der hypothetischen Gesamtstrafe die Einsatzstrafe für das schwerste Delikt festzulegen. Der Richter hat in einem ersten Schritt den Strafrahmen für die schwerste Straftat zu bestimmen und alsdann die Einsatzstrafe für diese Tat, unter Einbezug aller straferhöhenden und strafmindernden Umstände, innerhalb dieses Strafrahmens festzusetzen. In einem zweiten Schritt hat er diese Einsatzstrafe unter Einbezug der anderen Straftaten zu einer Gesamtstrafe zu erhöhen, wobei er ebenfalls den jeweiligen Umständen Rechnung zu tragen hat (BGE 6B_460/2010 vom 4. Februar 2011 E. 3.3.4 mit Hinweis). Die Vorinstanz geht von der Widerhandlung gegen das Bundesgesetz über die Ausländerinnen und Ausländer aus und legt hierfür den Strafrahmen fest. Somit geht sie nicht von der schwersten Tat aus. Als solche gilt jene, die gemäss abstrakter Strafdrohung des Gesetzes mit der höchsten Strafe bedroht ist, und nicht jene, die nach den konkreten Umständen verschuldensmässig am schwersten wiegt (<ref-ruling> E. 2c/bb). Die Vorinstanz hätte zunächst die Einsatzstrafe für die Widerhandlung gegen das Betäubungsmittelgesetz im Sinne von <ref-law>, die mit Freiheitsstrafe bis zu drei Jahren oder Geldstrafe bestraft wird, festlegen müssen. Damit folgt sie nicht dem gesetzlich vorgesehenen, methodischen Vorgehen. Hingegen ist nicht ersichtlich, dass sich die unrichtige Vorgehensweise zum Nachteil des Beschwerdeführers auswirkt. Auf die Aufhebung des Urteils in diesem Punkt kann daher verzichtet werden.
4.2.4 Die Vorinstanz fällt als Zusatzstrafe im Sinne von <ref-law> eine Freiheitsstrafe zu einer Geldstrafe als Grundstrafe aus. Ein solches Vorgehen entspricht nicht den von der bundesgerichtlichen Rechtsprechung entwickelten Grundsätzen für die Strafzumessung bei retrospektiver Konkurrenz. Bedingung für eine Zusatzstrafe ist stets, dass die Voraussetzungen der Gesamtstrafe nach <ref-law> erfüllt sind. Danach sind ungleichartige Strafen kumulativ zu verhängen, weil das Asperationsprinzip nur greift, wenn mehrere gleichartige Strafen ausgesprochen werden. Die Bildung einer Gesamtstrafe ist bei ungleichartigen Strafen nicht möglich (BGE 6B_460/2010 vom 4. Februar 2011 E. 4.3.1 mit Hinweisen). Als Zusatzstrafe zu der mit Urteil des Obergerichts des Kantons Zürich am 15. Oktober 2009 ausgesprochenen Grundstrafe käme demzufolge nur eine Geldstrafe in Betracht. Ist die Vorinstanz der Ansicht, es sei eine Freiheitsstrafe zu verhängen, muss sie eine eigenständige Strafe bilden. Zudem hat sie in diesem Falle hinreichend zu begründen, weshalb sie sich für eine Freiheitsstrafe anstelle einer Geldstrafe entscheidet (vgl. dazu <ref-ruling> E. 4.2 mit Hinweisen), und gegebenenfalls die Voraussetzungen nach <ref-law> zu berücksichtigen.
5. Die Beschwerde ist teilweise gutzuheissen, das vorinstanzliche Urteil aufzuheben und die Sache zu neuer Entscheidung zurückzuweisen. Im Übrigen ist sie abzuweisen.
Der Beschwerdeführer wird im Umfang seines Unterliegens kostenpflichtig (<ref-law>). Er ersucht jedoch um Gewährung der unentgeltlichen Rechtspflege und Verbeiständung. Seine finanzielle Bedürftigkeit ist ausgewiesen. Die Beschwerde war nicht von vornherein aussichtslos. Das Gesuch um unentgeltliche Rechtspflege ist daher gutzuheissen (<ref-law>). Somit sind keine Gerichtskosten zu erheben.
Der Beschwerdeführer ist aus der Bundesgerichtskasse zu entschädigen. Die Entschädigung ist dem Rechtsvertreter des Beschwerdeführers zuzusprechen.
Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen, das Urteil des Obergerichts des Kantons Zürich vom 16. November 2010 aufgehoben und die Sache im Sinne der Erwägungen zu neuer Entscheidung an die Vorinstanz zurückgewiesen. Im Übrigen wird die Beschwerde abgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege wird gutgeheissen.
3. Es werden keine Gerichtskosten erhoben.
4. Dem Rechtsvertreter des Beschwerdeführers, Rechtsanwalt Guido Hensch, wird für das bundesgerichtliche Verfahren eine Entschädigung von Fr. 3'000.-- aus der Bundesgerichtskasse ausgerichtet.
5. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Strafkammer, schriftlich mitgeteilt.
Lausanne, 29. April 2011
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Favre Horber