Sachverhalt: A. A.a. X._ trat am 1. Mai 1991 als "Leiter Wertschriften Verkauf Gesamtbank" in die A._-Bank ein, welche im Jahr 1993 von der B._-Bank übernommen wurde. Auf den 1. Januar 1999 wurde er zum "Vice President" und per 1. Januar 2000 zum "Director" der B._-Bank befördert. Innerhalb der Bank war er während der anklagerelevanten Phase für die Geschäftsbeziehung zur Finanzverwaltung des Kantons Zürich, Abteilung Vermögensverwaltung (VVKZ), zuständig, welche unter anderem für die Bewirtschaftung von Kapitalanlagen der C._ und das Vermögen des Reservefonds der D._ verantwortlich war. Am 1. November 2001 verliess er die Bank und trat eine Stelle als "Chief Investment Officer" bei der E._ AG an. Bereits am 24. Oktober 2001 hatte die VVKZ die E._ AG (bzw. X._ als deren Vertreter) ermächtigt, in ihrem Auftrag SMI-Transaktionen der C._ und der D._ bei der B._-Bank zu tätigen. Am 11./12. Dezember 2001 schloss der Kanton Zürich, vertreten durch die VVKZ, mit der E._ AG eine entsprechende Vereinbarung ab. Die E._ AG hatte mit der B._-Bank am 15./20. November 2001 hinsichtlich der Mandatierung einen Vertrag betreffend externe Vermögensverwaltung unterzeichnet, gemäss welchem eine Entschädigung der E._ AG in Form von Retrozessionszahlungen vereinbart wurde. A.b. X._ wird vorgeworfen, er habe bei Aktientransaktionen zum Nachteil der C._ und der D._ zu anderen als den effektiv an der Börse erzielten Kursen abgerechnet. Von der VVKZ habe er in einer ersten Phase als Mitarbeiter der B._-Bank und vom 29. November 2001 bis 6. Februar 2003 als Angestellter der E._ AG Handelsaufträge zur bestmöglichen und interessewahrenden Ausführung entgegengenommen. Diese habe er der Geschäftseinheit B._-Bank Privat Banking weitergeleitet mit der Anweisung, die Aufträge über mehrere Börsentage zu handeln. Diese seien über das Börsenhandelssystem in zahlreichen Teilausführungen abgewickelt worden. Die gekauften und verkauften Titel seien sodann zu den effektiv erzielten Preisen auf einem Handelsdepot der B._-Bank verbucht und dort bis zur vollständigen Ausführung des Auftrages zwischengelagert worden (sog. "warehousing"). X._ habe sich jeweils über die aktuellen Tageshöchst- bzw. Tagestiefstkurse und den "Volume Weighted Average Price" (volumengewichteter Durchschnittskurs aller in der konkreten Handelsperiode durch sämtliche Marktteilnehmer getätigten Transaktionen in einem gehandelten Titel; VWAP) informiert. Daraufhin habe er einen vom effektiv erzielten Durchschnittskurs zu Ungunsten von C._ und D._ geringfügig abweichenden Kurs festgelegt und diesen gegenüber der VVKZ abrechnen lassen. Der Abrechnungskurs sei handschriftlich auf den jeweiligen Handelsfichen im dafür vorgesehenen Feld "Titelkurs" eingetragen und im Datenverarbeitungssystem der Bank erfasst worden. Die der VVKZ übermittelten Abrechnungen hätten das Abschlussdatum der Transaktion, die Anzahl gehandelter Titel und den durch X._ bestimmten Abrechnungskurs beinhaltet. Die Faxabrechnung habe den Hinweis enthalten, dass es sich um die genauen Daten der ausgeführten Aufträge handle. Nebst den zu leistenden Abgaben sei bis zum 27. November 2000 auch die Höhe der vereinbarten Kommission von 0.08 % aufgeführt worden. Ab dem 24. August 2001 seien die Geschäfte "netto" abgerechnet und die Kommission nicht mehr separat ausgewiesen worden. Durch die Abrechnungen sei die VVKZ über die an der Börse effektiv erzielten Preise getäuscht worden. Gestützt darauf habe sie bei der F._-Bank Instruktionen für die Abwicklung der Transaktionen (sog. Settlement) erteilt. Dadurch sei es zu vermögensschädigenden Dispositionen zu Lasten der betreuten Portfolios der C._ und der D._ gekommen. Durch die Berücksichtigung einer auf die tatsächlich erzielten Kurse berechneten Kommission von 0.08 % sei bezüglich der am 24. August 2001 verbuchten Transaktionen (Transaktionen Nr. 152 bis 155 gemäss Anhang zur Anklage) ein Schaden von Fr. 105'352.65 entstanden. Gleichzeitig sei die B._-Bank in diesem Umfang unrechtmässig bereichert worden. Für die in der Zeit vom 29. November 2001 bis 6. Februar 2003 (Transaktionen Nr. 156 bis Nr. 196 gemäss Anhang zur Anklage) getätigten Transaktionen sei unter Berücksichtigung einer auf die tatsächlich erzielten Kurse berechneten und geschuldeten Kommission von 0.08 % in den Portfolios von C._ und D._ ein Schaden von insgesamt Fr. 4'949'948.80 entstanden. Der B._-Bank sei ein unrechtmässiger Ertrag in gleicher Höhe zugeflossen, aus welchem sie der E._ AG Retrozessionen im Umfang von Fr. 2'287'991.55 ausbezahlt habe. A.c. Das Bezirksgericht Zürich erklärte X._ am 20. November 2014 des mehrfachen Betrugs (Anklage Teil 1, Anklageziffern I. und II., Phasen 1a und 1b), des gewerbsmässigen Betrugs (Anklage Teil 1, Anklageziffer III., Phase 2) und der mehrfachen Urkundenfälschung (Anklage Teil 1, Anklageziffern I. bis III., Phasen 1a, 1b und 2) schuldig. Das Verfahren wegen mehrfachen Betrugs und Urkundenfälschung (Anklage Teil 1, Anklageziffer I., Transaktionen im Zeitraum vom 22. Mai bis 25. September 2000) stellte es infolge Verjährung ein. Es verurteilte X._ zu einer Freiheitsstrafe von 4 Jahren als Zusatzstrafe zu der mit Urteil des Obergerichts des Kantons Zürich vom 22. August 2014 ausgefällten Strafe. B. Das Obergericht des Kantons Zürich erklärte X._ am 28. April 2016 in zweiter Instanz in teilweiser Gutheissung seiner Berufung des Betrugs (Anklage Teil 1, Anklageziffer II., Phase 1b) und des gewerbsmässigen Betrugs (Anklage Teil 1, Anklageziffer III., Phase 2) schuldig und verurteilte ihn zu einer Freiheitsstrafe von 3 Jahren als Zusatzstrafe zur mit Urteil des Obergerichts vom 22. August 2014 ausgefällten Strafe. Das Verfahren in Bezug auf Anklage Teil 1, Anklageziffer I., Phase 1a (Transaktionen im Zeitraum vom 16. Oktober bis 27. November 2000) stellte es infolge Verjährung ein. Zudem sprach es ihn von der Anklage der mehrfachen Urkundenfälschung frei. C. X._ führt Beschwerde in Strafsachen. Er beantragt, er sei freizusprechen von den Vorwürfen des Betrugs (Anklage Teil 1, Anklageziffer II., Phase 1b) und des gewerbsmässigen Betrugs (Anklage Teil 1, Anklageziffer III., Phase 2). Eventualiter stellt er den Antrag auf Herabsetzung der Freiheitsstrafe als Zusatzstrafe zur mit Urteil des Obergerichts des Kantons Zürich vom 22. August 2014 ausgefällten Strafe auf ein Jahr Freiheitsstrafe. Subeventualiter seien Ziffer 3, 8 und 9 des angefochtenen Urteils aufzuheben, und es sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Schliesslich ersucht X._ um Gewährung der unentgeltlichen Rechtspflege. Das Obergericht hat auf eine Vernehmlassung verzichtet. Die Staatsanwaltschaft schliesst auf Abweisung der Beschwerde. X._ verzichtet auf eine Stellungnahme zur Vernehmlassung.