Sachverhalt: A. X._ wurde am 28. Juni 2000 vom Bezirksgericht Zürich wegen Vergehens und Verbrechens gegen das Betäubungsmittelgesetz (BetmG; SR 812.121) und Vergehens gegen das Bundesgesetz über Aufenthalt und Niederlassung von Ausländern (ANAG; AS 49 279) zu einer bedingten Gefängnisstrafe von 15 Monaten verurteilt. Am 21. April 2004 verurteilte ihn das Bezirksgericht Zürich erneut wegen Vergehens und Verbrechens gegen das Betäubungsmittelgesetz und mehrfachen Verweisungsbruchs zu einer Zuchthausstrafe von 2 Jahren und 6 Monaten. Die am 28. Juni 2000 bedingt ausgesprochene Freiheitsstrafe erklärte es als vollziehbar. X._ wurde nach dem Vollzug der beiden Strafen am 25. Dezember 2005 bedingt aus dem Strafvollzug entlassen, unter Ansetzung einer Probezeit von 3 Jahren. B. Am 9. September 2009 sprach das Bezirksgericht Zürich X._ erneut wegen mehrfacher qualifizierter Widerhandlung gegen das Betäubungsmittelgesetz, mehrfacher Übertretung des Betäubungsmittelgesetzes und mehrfacher Vergehen gegen das Ausländergesetz (AuG; SR 142.20) schuldig. Es bestrafte ihn unter Einbezug des Strafrests gemäss bedingter Entlassung vom 25. Dezember 2005 mit einer Gesamtfreiheitsstrafe von 4 1⁄2 Jahren. Das Obergericht des Kantons Zürich verurteilte X._ am 8. April 2010 auf dessen Berufung hin zu einer Freiheitsstrafe von 3 1⁄2 Jahren Freiheitsstrafe. Es verzichtete auf eine Rückversetzung in den Vollzug des Strafrests. C. Gegen dieses Urteil erhebt die Oberstaatsanwaltschaft des Kantons Zürich Beschwerde in Strafsachen. Sie beantragt, das angefochtene Urteil sei aufzuheben und X._ sei zu einer (Gesamt)freiheitsstrafe von 4 1⁄2 Jahren zu verurteilen. Eventualiter sei die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen. D. Das Obergericht des Kantons Zürich verzichtete auf eine Vernehmlassung. X._ reichte innert Frist keine Stellungnahme ein.