Faits : A. A.a. A.A._, né en 1975, et B.A._, née en 1976, se sont mariés le 6 juin 2003 à U._ (GE). Deux enfants sont issus de leur union, à savoir C._, née en 2004, et D._, né en 2007. Les parties vivent séparées depuis le 23 avril 2009. A.b. La vie séparée des époux a été organisée par un jugement de mesures protectrices de l'union conjugale du Tribunal de première instance du canton de Genève (ci-après: Tribunal), confirmé par la Cour de justice du canton de Genève (ci-après: Cour de justice) par arrêt du 18 juin 2010, attribuant la garde sur les enfants et la jouissance exclusive du domicile conjugal à B.A._ et instaurant une mesure de curatelle de surveillance et d'organisation du droit de visite. La Cour de justice a fixé le droit de visite de A.A._ à un week-end sur deux, du samedi matin 9h00 au dimanche soir 19h00, la moitié des vacances scolaires, ainsi qu'un mercredi sur deux dès 9h00 jusqu'au jeudi matin et un mercredi sur deux dès 18h00 jusqu'au jeudi matin. A.c. Le 21 juin 2011, A.A._ a déposé une demande en divorce concluant notamment à l'instauration de l'autorité parentale conjointe et d'une garde alternée s'exerçant une semaine sur deux. Dans sa réponse du 17 novembre 2011, B.A._ a notamment conclu à ce que l'autorité parentale et la garde sur les enfants lui soient attribuées et qu'un droit de visite s'exerçant un week-end sur deux, du samedi matin au dimanche soir à 18h00, un mercredi sur deux dès 18h30 jusqu'au jeudi matin et un mercredi sur deux dès 8h00 jusqu'au jeudi matin ainsi que durant la moitié des vacances scolaires soit réservé à A.A._. A.d. C._ a fait l'objet d'une évaluation de l'Office médico-pédagogique transmise au Tribunal le 13 décembre 2011. A.e. Le Service de protection des mineurs (ci-après: SPMi) a rendu un rapport d'évaluation le 30 avril 2012. Il a préconisé l'attribution à la mère de la garde et de l'autorité parentale sur les enfants et la fixation en faveur du père d'un droit de visite s'exerçant à raison d'un repas de midi par semaine, du mercredi soir au jeudi matin, une semaine sur deux et du mercredi midi au jeudi matin, au cours de la semaine suivante, un week-end sur deux du vendredi soir au lundi matin, ainsi que durant la moitié des vacances scolaires. A.f. Une expertise du groupe familial a été effectuée par le Centre universitaire romand de médecine légale, selon rapport daté du 22 avril 2013. Dans ce cadre, les experts se sont en particulier entretenus à plusieurs reprises avec les enfants ainsi qu'avec le Dr E._, psychiatre de C._. Les experts ont préconisé l'attribution de la garde à B.A._. Concernant le droit de visite du week-end, ils ont relevé que A.A._ devrait pouvoir continuer à bénéficier de son droit de visite actuel, lui permettant d'accueillir ses enfants à partir du vendredi soir pour le week-end. A.g. Par jugement du 3 février 2015, le Tribunal a, notamment, prononcé le divorce des époux (ch. 1 du dispositif), attribué à B.A._ l'autorité parentale et la garde sur C._ et D._ (ch. 2), réservé à A.A._ un droit de visite s'exerçant, sauf accord contraire des parties, à raison d'un week-end sur deux du vendredi après l'école au dimanche soir 18h30, du mercredi après l'école au jeudi matin à l'école et durant la moitié des vacances scolaires (ch. 3) et maintenu la curatelle d'organisation et de surveillance du droit de visite au sens de l'art. 308 al. 2 CC (ch. 4). B. B.a. Par courriel du 11 février 2015, une intervenante du SPMi a fait savoir à B.A._ qu'elle avait rencontré les enfants des parties le jour même et qu'elle ne voyait pas l'intérêt de les rencontrer à nouveau. Un entretien était prévu en fin d'année. B.b. Le 21 avril 2015, le Dr E._ a adressé à A.A._, avec copie à B.A._, un courrier dans lequel il relevait notamment que l'enfant C._ avait été ébranlée par la réglementation du jugement de divorce du 3 février 2015 concernant les droits parentaux et le droit de visite. L'attribution de l'autorité parentale à sa seule mère représentait pour C._ " un déchirement, une disqualification incompréhensible de son père et un déni de son origine paternelle ". L'enfant exprimait " sa souffrance intime à ce que son père ne puisse valablement la représenter ". " La valeur symbolique et juridique de cette décision qui concern[ait] son lien à son père " était considérable. Il proposait par conséquent qu'il soit procédé à une réévaluation de la situation par le SPMi, lequel avait la compétence d'entendre l'enfant en toute indépendance. Par courriel du 6 mai 2015, B.A._ a fait savoir à son ex-époux que, C._, informée du contenu de la lettre du Dr E._, avait indiqué à sa mère qu'elle ne comprenait pas la moitié du contenu de ce document et qu'elle disait à son psychiatre ce que son père lui disait de dire pour ne pas le fâcher. C. C.a. Par acte déposé par-devant la Cour de justice le 5 mars 2015, B.A._ a fait appel du jugement du 3 février 2015, sollicitant notamment l'annulation du ch. 3 de son dispositif. A titre principal, elle a requis la fixation en faveur de son ex-époux d'un droit de visite s'exerçant, à défaut d'accord contraire entre les parties, une semaine sur deux du mercredi de la sortie de l'école jusqu'au retour à l'école le jeudi matin et, la semaine suivante, le mercredi de 18h00 jusqu'au retour à l'école le jeudi matin, un week-end sur deux du vendredi 18h00 au dimanche 18h30 ainsi que durant la moitié des vacances scolaires. C.b. Dans sa réponse à l'appel déposée le 7 mai 2015, A.A._ a conclu au déboutement de sa partie adverse de toutes ses conclusions avec suite de frais. Le même jour, il a déposé un appel joint, concluant, à titre préalable, à ce que la Cour de justice ordonne au SPMi d'effectuer une nouvelle évaluation de la situation des enfants et procède à l'audition de C._. A titre principal, il a sollicité l'annulation des ch. 2 et 3 du dispositif du jugement querellé et a conclu à ce que la Cour de justice maintienne l'autorité parentale conjointe sur les enfants et lui réserve un droit de visite s'exerçant, à défaut d'accord contraire des parties, tous les mercredis de la sortie de l'école au jeudi matin à l'école, un week-end sur deux du vendredi après l'école au lundi matin à l'école et pendant la moitié des vacances scolaires, avec suite de frais et dépens. C.c. Par arrêt du 30 octobre 2015, la Cour de justice a confirmé le jugement attaqué. D. Par acte du 7 décembre 2015, A.A._ interjette un recours en matière civile au Tribunal fédéral contre l'arrêt du 30 octobre 2015 concluant principalement à son annulation et à sa réforme en ce sens qu'il soit dit que l'autorité parentale sur les enfants C._ et D._ sera " partagée "; subsidiairement, il conclut au renvoi de la cause à l'autorité cantonale pour qu'il soit procédé à l'audition de C._ et qu'une nouvelle décision au sens des considérants soit rendue. Invitées à se déterminer sur le recours, la Cour de justice s'est référée aux considérants de son arrêt et l'intimée a conclu à son rejet. Le recourant a répliqué en date du 17 juin 2016. L'intimée a dupliqué le 28 juin 2016.