Faits : A. A.A._ (1982) et B.A._ (1983), tous deux de nationalité roumaine, se sont mariés le 9 septembre 2007. De leur union est issue une fille, C.A._, née en 2008. La famille a d'abord vécu en Roumanie, puis les époux A._ sont venus s'installer en Suisse au mois d'octobre 2012. L'enfant est demeurée chez sa grand-mère paternelle en Roumanie, jusqu'à l'automne 2013, où elle a rejoint ses parents en Suisse. Les époux A._ ont suspendu définitivement la vie commune le 17 octobre 2013. Le père est retourné seul en Roumanie. A.a. Par ordonnance de mesures superprovisionnelles du 22 novembre 2013, le Président du Tribunal d'arrondissement de la Broye et du Nord vaudois, saisi par la mère, a attribué la garde de l'enfant commun à la mère et suspendu le droit aux relations personnelles entre l'enfant et le père. A.b. A la fin de l'année 2013, la mère a introduit action en divorce en Roumanie. Par jugement du 30 janvier 2014, exécutoire dès son prononcé, le Tribunal civil de Y._ (RO) a ratifié l'accord de médiation survenu le 17 décembre 2013 et, partant, a prononcé le divorce des époux A._, maintenu l'autorité parentale conjointe des père et mère, attribué la garde de l'enfant au père, sous réserve d'un droit de visite de la mère, et fixé le lieu de résidence de l'enfant auprès du père. A.c. Le 20 décembre 2013, la fille des parties a été confiée à son père en Roumanie. L'enfant est demeurée vivre auprès de son père et la mère a exercé son droit de visite à deux ou trois reprises. La fille a fréquenté l'école maternelle de Y._ (RO) jusqu'au 1 er avril 2015. En 2014 et début 2015, le père a cependant séjourné en Suisse. Durant l'absence du père de Roumanie, le Tribunal civil de Y._ (RO) a "délégué" l'autorité parentale sur l'enfant à la grand-mère paternelle. Lorsque le père a regagné la Roumanie, il a à nouveau vécu avec sa fille, auprès de sa mère. A.d. Par ordonnance de mesures protectrices de l'union conjugale du 10 février 2014, le Président du Tribunal d'arrondissement de la Broye et du Nord vaudois a confié la garde de l'enfant à la mère et institué un droit de visite surveillé du père. La mère a sollicité la reconnaissance de ce prononcé auprès des autorités roumaines. Statuant le 3 mars 2015, la Cour d'appel de Z._ (RO) a rejeté la demande, considérant que la cause avait déjà été jugée par le tribunal roumain, dont le jugement exécutoire l'emportait sur le prononcé postérieur de l'autorité suisse. A.e. Par ordonnance pénale du 24 avril 2014, le Ministère public de l'arrondissement de La Côte a reconnu le père coupable de voies de fait qualifiées, d'injure et de menaces qualifiées à l'endroit de son ex-épouse. A.f. Le 15 octobre 2014, la mère a introduit une action en modification du jugement de divorce en Roumanie, tendant à obtenir l'autorité parentale et le transfert, chez elle, du lieu de résidence de la fille. A.g. Le 17 avril 2015, le père a subi, lors d'une agression, un traumatisme crânien, des contusions cérébrales, ainsi qu'une hémorragie sous-anachnoïdienne. Lors de son admission à l'hôpital, il était en état d'ébriété avancé, était agité et présentait des " phénomènes de sevrage (alcool + drogues) ". Il est demeuré hospitalisé jusqu'au 21 avril 2015. A.h. Le 28 avril 2015, le père a déclaré, par écrit, qu'il consentait à ce que sa fille " voyage en Suisse, accompagnée de sa mère ", spécifiant que ce document " lui était nécessaire à la Police des frontières, afin de sortir du pays, ainsi que partout où il sera nécessaire ". L'autorisation était délivrée pour une année, du 28 avril 2015 au 28 avril 2016. Ce titre a été établi et légalisé en l'étude d'un notaire de Y._ (RO), lequel a certifié que le père avait compris le contenu de sa déclaration et qu'elle représentait sa volonté. Par déclaration notariée du 12 août 2015, le père a révoqué l'autorisation précitée du 28 avril 2015. A.i. Au mois d'avril 2015, l'enfant est revenue en Suisse avec sa mère. Dès le mois d'août 2015, elle a été scolarisée à l'école primaire de U._ (VS), en Suisse. A.j. Le 14 août 2015, le père a déposé une requête en retour de l'enfant auprès de l'autorité centrale roumaine. Le 29 février 2016, le Ministère de la justice de Roumaine a signifié à l'Office fédéral de la justice de la Confédération suisse la " demande de restitution " de l'enfant présentée par le père. A.k. Par arrêt du 3 mars 2016, le Tribunal civil de Y._ a, après avoir procédé à l'audition de témoins et sollicité un rapport de l'autorité de protection de l'enfant, attribué l'autorité parentale et la garde de la fille des parties à la mère, mettant en évidence les antécédents judiciaires du père, sa consommation fréquente d'alcool et de stupéfiants, sa prédisposition au scandale, et sa violence verbale et physique manifestée à l'encontre de son ex-femme. Le tribunal roumain a également exposé que, à la suite du traumatisme crânien subi en avril 2015, le père n'était plus à même de prendre soin de sa fille, que la révocation de l'autorisation du 28 avril 2015, peu de temps après l'avoir consentie, constituait un comportement inconséquent, qu'il était incapable de prendre les décisions de nature à servir le bien de l'enfant et qu'il bénéficiait de l'aide de ses parents. B. Le 21 avril 2016, A.A._ a adressé une requête en retour de l'enfant mineur au Tribunal cantonal du canton du Valais et sollicité le prononcé de mesures provisoires immédiates. B.a. Le 25 avril 2016, le Juge unique de la Cour civile II du Tribunal cantonal du canton du Valais a fait interdiction à la mère de quitter le territoire du Valais avec l'enfant des parties ou de faire déplacer celle-ci en dehors du territoire du canton du Valais, jusqu'à droit connu sur le sort de la requête en retour de l'enfant. L'enfant a été entendue par sa curatrice au mois de mai 2016, sans donner l'impression d'avoir été instrumentalisée, et déclaré qu'elle souhaitait demeurer auprès de sa mère, qu'elle était certes attachée à son père et à sa grand-mère paternelle, mais qu'elle craignait que son père la ramène en Roumanie. Le 6 juin 2016, le père a versé à la cause la déclaration d'appel qu'il avait déposée le 26 mai 2016 contre le jugement du 3 mars 2016 du Tribunal civil de Y._. B.b. Statuant par décision du 14 juillet 2016, le Juge unique de la Cour civile II du Tribunal cantonal du canton du Valais a rejeté la requête en retour de l'enfant. C. Par acte du 27 juillet 2016, A.A._ interjette un recours en matière civile au Tribunal fédéral. Il conclut à l'annulation du jugement querellé et à sa réforme en ce sens que le retour de l'enfant C.A._ en Roumanie est ordonné, aux frais de la mère, le cas échéant, avec le concours de la force publique. Il requiert en outre la gratuité de la procédure fédérale, une indemnité de dépens à la charge du Tribunal fédéral et le remboursement de ses frais (voyage, représentation, recherche de l'enfant), par la mère. D. Invitées à se déterminer sur le recours, l'intimée, de même que la curatrice de l'enfant, ont conclu toutes deux au rejet du recours, sous réserve toutefois de l'admission de la conclusion tendant à ce qu'il ne soit pas perçu de frais de procédure. Quant au juge cantonal, il a déclaré se référer aux considérants de son arrêt.