Sachverhalt: A. Das Bezirksgericht Zürich erklärte X._ am 19. August 2015 der versuchten schweren Körperverletzung, der Sachbeschädigung sowie der mehrfachen Übertretung des Betäubungsmittelgesetzes schuldig. Es bestrafte ihn mit einer unbedingten Freiheitsstrafe von 42 Monaten und einer Busse von Fr. 800.--. Sowohl X._ (amtlich verteidigt durch Rechtsanwalt A._) als auch die Staatsanwaltschaft erhoben gegen dieses Urteil Berufung. B. Das Obergericht des Kantons Zürich setzte am 18. März 2016 die Berufungsverhandlung auf den 23. Mai 2016 fest und lud die Parteien vor. Am 10. Mai 2016 teilte Rechtsanwalt Jürg Federspiel dem Obergericht mit, X._ habe ihn neu mit der erbetenen Verteidigung im Berufungsverfahren beauftragt. Er beantragte, es seien ihm die Akten zur Einsicht zuzustellen und der Termin der Berufungsverhandlung sei neu anzusetzen. Gleichzeitig beantragte Rechtsanwalt Jürg Federspiel, der bisherige amtliche Verteidiger sei aus seiner Pflicht zu entlassen. Das Obergericht verfügte am 11. Mai 2016, es werde vorgemerkt, dass X._ neu durch Rechtsanwalt Jürg Federspiel erbeten verteidigt werde. Die Gesuche um Entlassung des bisherigen amtlichen Verteidigers und Verschiebung der Berufungsverhandlung wies es ab. C. Die Berufungsverhandlung fand am 23. Mai 2016 in Abwesenheit von Rechtsanwalt Jürg Federspiel statt. Rechtsanwalt A._ beantragte unter anderem, die Verhandlung sei abzubrechen und ein neuer Gerichtstermin sei festzusetzen. Das Obergericht lehnte diesen Antrag ab. Es stellte fest, dass die erstinstanzlichen Schuldsprüche wegen Sachbeschädigung und mehrfacher Übertretung des Betäubungsmittelgesetzes in Rechtskraft erwachsen waren. Es sprach X._ zudem der versuchten schweren Körperverletzung schuldig und bestrafte ihn mit einer unbedingten Freiheitsstrafe von 42 Monaten sowie einer Busse von Fr. 800.--. D. X._ führt Beschwerde in Strafsachen. Im Hauptpunkt beantragt er, die Sache sei zur Durchführung einer neuen Berufungsverhandlung in Anwesenheit seines Wahlverteidigers an die Vorinstanz zurückzuweisen. Der Beschwerde sei die aufschiebende Wirkung zu erteilen; ihm sei die unentgeltliche Rechtspflege und Verbeiständung zu gewähren. E. Das Bundesgericht lehnte den Antrag um unentgeltliche Rechtspflege und Verbeiständung am 31. Januar 2017 ab. Das Obergericht und die Oberstaatsanwaltschaft des Kantons Zürich verzichten auf eine Vernehmlassung.