Faits: A. A.a B._, ressortissante grecque, et A._, d'origine grecque également, se sont mariés le 18 mars 2011 à V._, en Grèce. L'épouse a séjourné en Suisse du 19 juillet 2010 au 4 janvier 2011 et travaillé durant cette période en tant que médecin interne de D._. Enceinte, elle est retournée en Grèce où elle a repris son activité auprès de E._. A.b Le 20 juillet 2011, B._ a donné naissance à C._, à New-York où elle s'est rendue le 10 juin 2011 après un séjour de trois semaines auprès de sa s?ur à Genève. Le 31 août 2011, la mère et l'enfant sont retournées à Genève alors que A._, qui s'était rendu à New-York le 21 juillet 2011, était rentré seul en Grèce le 22 août 2011. A.c Depuis le 1er novembre 2011, B._ est employée pour une durée indéterminée par F._; elle est inscrite avec son enfant au Service du contrôle des habitants de Lausanne depuis cette même date. La mère et l'enfant sont en outre titulaires d'une autorisation de séjour (permis B) depuis respectivement le 28 novembre 2011 et le 2 mars 2012. A.d En date du 4 novembre 2011, A._ a saisi le Ministère grec de la justice d'une plainte pour déplacement et non-retour illicite de l'enfant, laquelle a été transmise à l'Office fédéral de la justice (OFJ). L'OFJ a rejeté la requête par décision du 2 décembre 2011 pour le motif que l'enfant n'avait jamais eu de résidence habituelle en Grèce. A.e Le 16 décembre 2011, B._ a ouvert une procédure de mesures protectrices de l'union conjugale devant le Président du Tribunal civil de l'arrondissement de Lausanne. La garde sur sa fille lui a été attribuée, à titre superprovisionnel, par ordonnance du 25 janvier 2012. A.f A._ a quant à lui déposé une demande en divorce auprès du Tribunal collégial de première instance d'Athènes le 28 décembre 2011. Il a obtenu un droit de visite sur C._ au domicile de la mère situé, selon les indications de la requête, en Grèce par ordre provisoire du 21 février 2012. A.g Depuis le mois de septembre 2011, A._ est venu à plusieurs reprises en Suisse pour voir l'enfant. Il est en outre en contact régulier avec celle-ci et son épouse par le biais de Skype. B. B.a Par requête du 20 mars 2012 adressée à la Chambre des tutelles du Tribunal cantonal du canton de Vaud, A._ a conclu à ce que le retour de l'enfant C._ soit immédiatement ordonné à son domicile et à ce qu'ordre soit donné à la mère, sous la menace de la peine d'amende prévue à l'art. 292 CP, de remettre immédiatement l'enfant au Service de protection de la jeunesse (ci-après: SPJ) afin que celui-ci se charge de la lui remettre, respectivement se charge du rapatriement de l'enfant auprès de lui en Grèce, l'exécution pouvant intervenir, si nécessaire, avec le concours de la force publique. B.b Le 21 mars 2012, la Chambre des tutelles du Tribunal cantonal du canton de Vaud a désigné Me Catherine Jaccottet Tissot, avocate à Lausanne, en qualité de curatrice de l'enfant pour la procédure de retour. B.c Par arrêt du 3 mai 2012, la Chambre des tutelles du Tribunal cantonal du canton de Vaud a rejeté la requête en retour formée par A._. C. Le 14 mai 2012, A._ exerce un recours en matière civile au Tribunal fédéral contre cet arrêt, concluant à sa réforme en ce sens que la requête en retour déposée est admise. Subsidiairement, il conclut à son annulation et au renvoi de la cause pour nouvelle décision. À l'appui de ses conclusions, il se plaint d'arbitraire dans l'établissement des faits ainsi que dans le résultat auquel est parvenue l'autorité inférieure. Il invoque également une violation des art. 13 et 36 Cst. ainsi que 8 CEDH. Invitées à se déterminer sur le recours, la mère et la curatrice de l'enfant concluent à son rejet; la curatrice sollicite en outre l'octroi de l'assistance judiciaire. La cour cantonale se réfère aux considérants de son arrêt. 