Sachverhalt: A. X._ lebt getrennt von seiner ehemaligen Lebenspartnerin A._. Die beiden gemeinsamen Kinder wohnten bis am 15. Oktober 2011 bei der Mutter, wobei die Eltern die gemeinsame elterliche Sorge innehatten. Die Staatsanwaltschaft IV des Kantons Zürich wirft X._ vor, die Kinder am 15. Oktober 2011 im Rahmen seines Besuchsrechts abgeholt zu haben, mit ihnen ohne Wissen und Zustimmung der Mutter sowie der Beiständin nach Nigeria gereist zu sein und sie dort bei Familienangehörigen zurückgelassen zu haben. Dies in der Absicht, die Kinder dort aufziehen zu lassen, bis ihm durch die schweizerischen Behörden die alleinige elterliche Sorge übertragen werde. B. In Bestätigung des Urteils des Bezirksgerichts Zürich vom 3. Juni 2013 sprach das Obergericht des Kantons Zürich X._ am 13. Januar 2014 der mehrfachen qualifizierten Freiheitsberaubung und des mehrfachen Entziehens von Minderjährigen schuldig. Es verurteilte ihn zu einer Freiheitsstrafe von sieben Jahren. Zudem entschied es über den Widerruf einer bedingt ausgesprochenen Geldstrafe und die Zivilforderungen von A._. Das Bundesgericht hiess die Beschwerde in Strafsachen von X._ am 2. Dezember 2014 teilweise gut, hob das Urteil des Obergerichts vom 13. Januar 2014 auf und wies die Sache zur neuen Entscheidung an dieses zurück (Verfahren 6B_123/2014). Das Bundesgericht erwog unter anderem, der Tatbestand der Freiheitsberaubung sei nicht erfüllt. Demgegenüber seien die objektiven Tatbestandsmerkmale der Entführung gemäss Art. 183 Ziff. 2 StGB gegeben. Ob dieser Tatbestand auch in subjektiver Hinsicht erfüllt sei, müsse die Vorinstanz nach ergänzter Sachverhaltsfeststellung beurteilen. C. Mit Urteil vom 21. Oktober 2015 stellte das Obergericht unter anderem fest, dass sein Urteil vom 13. Januar 2014 hinsichtlich des Schuldspruchs wegen mehrfachen Entziehens von Minderjährigen in Rechtskraft erwachsen war. Es verurteilte X._ wegen mehrfacher qualifizierter Entführung zu einer Freiheitsstrafe von sieben Jahren und widerrief den mit seinem Urteil vom 8. Juni 2012 gewährten bedingten Strafvollzug. Ferner stellte es fest, dass X._ A._ dem Grundsatze nach schadenersatzpflichtig ist, und verpflichtete ihn, ihr eine zu verzinsende Genugtuung von Fr. 30'000.-- zu bezahlen. Es auferlegte die Kosten des ersten Berufungsverfahrens X._, wobei es die Kosten der amtlichen Verteidigung sowie der unentgeltlichen Verteidigung von A._ einstweilen auf die Gerichtskasse nahm und die Rückzahlungspflicht im Sinne von Art. 135 Abs. 4 StPO vorbehielt. D. X._ beantragt mit Beschwerde in Strafsachen, das Urteil des Obergerichts vom 21. Oktober 2015 sei vollumfänglich aufzuheben und er sei vom Vorwurf der mehrfachen qualifizierten Entführung freizusprechen. Eventualiter sei er, unter Anrechnung der erstandenen Haft, mit einer Freiheitsstrafe von maximal 42 Monaten zu bestrafen. Der Kanton Zürich sei zu verpflichten, ihm eine Genugtuung von mindestens Fr. 120.-- pro Tag Überhaft und eine Entschädigung von Fr. 15'000.-- zu bezahlen. Die Genugtuung für A._ sei auf Fr. 10'000.-- zu reduzieren und die Kosten ihrer unentgeltlichen Verbeiständung seien definitiv dem Kanton Zürich aufzuerlegen. Subeventualiter sei die Sache zur neuen Entscheidung an das Obergericht zurückzuweisen. Ferner ersucht er um unentgeltliche Rechtspflege und Verbeiständung.