Sachverhalt: A. X._ (Ehemann; geb. 1983) und Y._ (Ehefrau; geb. 1982) heirateten am 3. Mai 2004 in D._ (USA). Sie sind die Eltern der gemeinsamen Kinder A._ (geb. xx.xx.2005) und B._ (geb. xx.xx.2010). Seit dem Eheschluss lebte die Familie zusammen an verschiedenen Orten in den USA. Beide Eltern sind US-Staatsbürger; die Mutter ist zudem portugiesische Staatsangehörige. B. Am 27. Mai 2012 reiste Y._ zusammen mit ihren zwei Kindern von C._ (USA) über Spanien nach Italien. Der Rückflug war für den 6. August 2012 vorgesehen. In Italien besuchte Y._ vorerst ihre (kranke) Mutter. Mit ihr und den Kindern reiste sie anschliessend zur Erholung nach Portugal und von dort am 26. Juli 2012 zu medizinischen Abklärungen in die Schweiz. C. C.a. Mit Schreiben vom 16. Januar 2013 gelangte der Kläger an die Zentralbehörde der USA und stellte ein Begehren um Rückführung der Kinder A._ und B._ in die USA. Die US-amerikanische Zentralbehörde übermittelte den Antrag mit Schreiben vom 24. Januar 2013 an das Bundesamt für Justiz als schweizerische Zentralbehörde. C.b. Mit Eingabe vom 2. August 2013 machte X._ beim Obergericht des Kantons Zürich ein Rückführungsverfahren betreffend seine beiden Kinder A._ und B._ anhängig. Das Obergericht wies das Rückführungsbegehren mit Urteil vom 16. Oktober 2013 ab. Das begründete Urteil ging am 21. Oktober 2013 bei X._ ein. D. X._ (Beschwerdeführer) gelangt mit Beschwerde vom 31. Oktober 2013 an das Bundesgericht. Er verlangt die Aufhebung des vorinstanzlichen Urteils (Ziff. 1) und die Feststellung, dass Y._ (Beschwerdegegnerin) die gemeinsamen Kinder A._ und B._ seit dem 6. August 2012 widerrechtlich in der Schweiz zurückhält (Ziff. 2). Zudem sei die Rückführung der Kinder innert fünf Tagen ab Rechtskraft des bundesgerichtlichen Entscheides in die USA anzuordnen (Ziff. 3) und die Beschwerdegegnerin zu verpflichten, die Kinder in die USA zurückzubringen (Ziff. 4). Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen (Ziff. 5). Ferner verlangt der Beschwerdeführer superprovisorisch die Hinterlegung der Ausweispapiere der Kinder (Ziff. 6 und 6a). Schliesslich beantragt er, ihm für das bundesgerichtliche Verfahren Rechtsanwältin Julia Geschwend als unentgeltliche Rechtsvertreterin zu bestellen. Am 4. November 2013 verfügte das Bundesgericht superprovisorisch, dass die Ausweispapiere für die beiden Kinder während des bundesgerichtlichen Verfahrens hinterlegt zu bleiben haben. Nach Einholung von Vernehmlassungen erteilte der Instruktionsrichter am 20. November 2013 der Beschwerde im Umfang der superprovisorisch verfügten Massnahme aufschiebende Wirkung. Das Obergericht hat darauf verzichtet, sich zur Sache vernehmen zu lassen. Der Kindesvertreter beantragt in seiner Eingabe vom 14. November 2013, die Beschwerde vollumfänglich abzuweisen. Den gleichen Standpunkt nimmt die Beschwerdegegnerin in ihrer Stellungnahme vom 18. November 2013 ein. Für den Fall einer Gutheissung der Beschwerde beantragt die Beschwerdegegnerin die Rückweisung an die Vorinstanz, damit zusätzlich die Möglichkeiten der Mutter geprüft werden, mit ihren Kindern in den USA zu leben. Sowohl der Kindesvertreter als auch die Beschwerdegegnerin haben zusätzlich für das bundesgerichtliche Verfahren die unentgeltliche Rechtspflege beantragt. Die in der Vernehmlassung eingegangenen Stellungnahmen sind dem Beschwerdeführer am 20. November 2013 zur Wahrung seines Replikrechts zugestellt worden. 