Citation: 5A_666/2016 E. B

Par acte du 14 septembre 2016, le père exerce un recours en matière civile au Tribunal fédéral. Il conclut, " avec suite de dépens de toutes les instances ", à la réforme de l'arrêt attaqué en ce sens qu'il est dit qu'il n'a pas à contribuer à l'entretien de sa fille B.________. Subsidiairement, il conclut à l'annulation de l'arrêt cantonal et au renvoi de la cause à l'autorité précédente pour nouvelle décision dans le sens des considérants. Il sollicite également le bénéfice de l'assistance judiciaire pour la procédure fédérale. Invitées à se déterminer, l'intimée a conclu au rejet du recours et a requis le bénéfice de l'assistance judiciaire et la Cour d'appel civile a déclaré se référer aux considérants de son arrêt.