Sachverhalt: A. Y._ suchte am 8. Juni 2009 um ca. 18 Uhr mit einem Revolver bewaffnet das Lokal "Z._" an der M._-Strasse in Zürich-Seebach auf. Er ging dort auf X._ los und schlug mit der Waffe auf ihn ein. Während des darauf folgenden Handgemenges gab Y._ zwei Schüsse ab. Der erste verfehlte das Opfer, der zweite traf es am Hals und führte zu einem oberflächlichen Durchschuss. Y._ verliess darauf fluchtartig das Lokal und rannte mit der Waffe in der Hand weg. X._ behändigte ebenfalls einen Revolver und setzte ihm nach. Nachdem Y._ seinen Verfolger bemerkt hatte, zielte er aus einer Entfernung von ca. 10 bis 15 Metern auf diesen und drückte ein weiteres Mal ab. Ebenso schoss X._ auf seinen Kontrahenten. Beide Schüsse verfehlten den Gegner. B. Das Obergericht des Kantons Zürich verurteilte Y._ am 19. Dezember 2012 zweitinstanzlich der mehrfachen versuchten vorsätzlichen Tötung. Strittig war der Schusswechsel auf der M._-Strasse. Unangefochten und nicht zu prüfen war der erstinstanzliche Schuldspruch der versuchten vorsätzlichen Tötung im Lokal "Z._". Gleichzeitig stellte das Obergericht fest, dass der erstinstanzliche Entscheid insbesondere betreffend den Schuldspruch der mehrfachen Gefährdung des Lebens und der Widerhandlung gegen das Waffengesetz in Rechtskraft erwachsen war. Es verurteilte Y._ zu einer Freiheitsstrafe von 11 Jahren unter Anrechnung der Untersuchungshaft und des vorzeitigen Strafvollzugs von 1290 Tagen. C. Y._ führt Beschwerde in Strafsachen. Er beantragt, das Urteil des Obergerichts des Kantons Zürich sei im Strafpunkt aufzuheben, und die Sache sei zur Neubeurteilung an die Vorinstanz zurückzuweisen. Zudem ersucht er um Gewährung der unentgeltlichen Rechtspflege und Verbeiständung. D. Das Obergericht des Kantons Zürich hat auf Vernehmlassung verzichtet. Die Staatsanwaltschaft IV des Kantons Zürich beantragt die Bestätigung des angefochtenen Entscheids und lässt sich im Übrigen nicht vernehmen.