Sachverhalt: A. X._ reiste am 12. April 2012 zusammen mit Y._ von Buenos Aires (Argentinien) über Sao Paulo (Brasilien) nach Zürich-Kloten. Sie hatten die Absicht, nach Brüssel (Belgien) weiter zu fliegen. Bei einer polizeilichen Kontrolle im Transitbereich des Flughafens konnte festgestellt werden, dass Y._ insgesamt 709 Gramm Kokaingemisch mit einem Reinheitsgehalt von 92% bzw. 93% in ihrem Körper mit sich führte. B. Die Anklage wirft X._ vor, den Kokaintransport organisiert, den Kontakt zum Auftraggeber "Joker" hergestellt, die Drogen in Argentinien von einem Lieferanten entgegengenommen, diese an Y._ übergeben und die Drogenkurierin auf der ganzen Reise begleitet und beaufsichtigt zu haben. X._ bestreitet dies und macht geltend, er habe keine Kenntnis vom Drogentransport seiner Freundin gehabt. C. Das Bezirksgericht Bülach verurteilte X._ am 29. August 2012 im Wesentlichen gestützt auf die Aussagen von Y._ wegen qualifizierter Widerhandlung gegen das Betäubungsmittelgesetz zu einer Freiheitsstrafe von 36 Monaten. Es schob den Vollzug der Freiheitsstrafe im Umfang von 20 Monaten auf. Auf Berufung von X._ bestätigte das Obergericht des Kantons Zürich das erstinstanzliche Urteil. D. X._ führt Beschwerde in Strafsachen. Er beantragt, das angefochtene Urteil sei aufzuheben, er sei von der Anklage freizusprechen und es sei ihm eine angemessene Entschädigung zuzusprechen. X._ stellt ein Gesuch um unentgeltliche Rechtspflege. E. Das Obergericht und die Oberstaatsanwaltschaft des Kantons Zürich haben auf eine Vernehmlassung verzichtet. Die Strafrechtliche Abteilung des Bundesgerichts hat die Angelegenheit am 14. Februar 2014 an einer öffentlichen Sitzung beraten. 