Faits : A. Par jugement du 1 er avril 2015, le Tribunal de police du canton de Genève a acquitté X._ des chefs d'actes d'ordre sexuel avec des enfants et d'actes d'ordre sexuel commis sur une personne incapable de discernement ou de résistance, condamné l'Etat de Genève à verser à X._ 16'000 fr. à titre d'indemnité pour les dépens occasionnés par l'exercice raisonnable de ses droits de procédure, 200 fr. à titre de réparation du tort moral subi du fait de sa privation de liberté et rejeté les conclusions civiles de A._, laissant les frais de procédure à la charge de l'Etat. B. Statuant par arrêt du 16 octobre 2015 sur les appels formés par le Ministère public du canton de Genève, par A._, ainsi que par X._ contre le jugement du 1 er avril 2015, la Chambre pénale d'appel et de révision de la Cour de justice du canton de Genève a rejeté l'appel de ce dernier et admis ceux des deux autres parties. Elle a en conséquence annulé le jugement entrepris qu'elle a réformé en ce sens qu'elle a reconnu X._ coupable d'actes d'ordre sexuel avec des enfants, l'a acquitté du chef d'actes d'ordre sexuel commis sur une personne incapable de discernement ou de résistance, l'a condamné à une peine pécuniaire de 180 jours-amende à 30 fr. chacun, sous déduction d'un jour-amende correspondant à un jour de détention subie avant jugement et l'a mis au bénéfice du sursis, fixant le délai d'épreuve à deux ans. Elle a en outre condamné X._ à verser à A._ la somme de 7'000 fr. avec intérêts à 5% dès le 1 er décembre 2006, à titre d'indemnité pour tort moral, ainsi que la somme de 10'044 fr. pour les dépenses occasionnées par la procédure de première instance, respectivement 4'941 fr. pour celles de la procédure d'appel. En substance, les faits retenus sont les suivants. B.a. En 2006, X._ a commis des attouchement à caractère sexuel sur A._, née en 1997. X._ a été le compagnon de la mère de A._, B._, entre 2004 et octobre 2010. B.b. Alors que B._ était sortie avec une amie, laissant sa fille avec X._, ce dernier a embrassé la fillette dans le cou, lui a ôté son pyjama et l'a touchée sur tout le corps. Passant sa main sous sa culotte, il lui a ensuite introduit un ou deux doigts dans le vagin et l'a appelée " B._ ". En rentrant, B._ a trouvé trois bouteilles de vin rouge vides dans la cuisine. Le lendemain matin, elle a réveillé sa fille qui n'allait pas bien et qui lui a confié que cela s'était mal passé la veille avec X._ qui lui avait donné une fessée. Sa fille ne lui a rien dit de plus jusqu'en octobre 2009. Elle l'a alors mise en relation avec son médecin-psychiatre, le Dr C._ qui lui a conseillé de porter plainte, ce qu'elle n'a pas fait dans l'immédiat. B.c. En proie à des idées noires, A._, qui n'allait pas bien depuis octobre 2010, a été hospitalisée durant une semaine aux Hôpitaux universitaires de Genève (ci-après: HUG). Elle a commencé une thérapie avec le Dr D._, psychiatre indépendant recommandé par les HUG, à qui elle a parlé des gestes déplacés susmentionnés. Elle a également parlé des attouchements dont elle a été victime à l'un des conseillers sociaux du Cycle d'orientation de E._. Elle a fait une tentative de suicide en avril 2012. Depuis novembre 2012, elle a été suivie par une collaboratrice du Dr F._, soit la psychologue G._, qu'elle a vue à raison de deux à trois fois par semaine. Sur conseil de cette dernière, B._ s'est présentée le 21 décembre 2012 à la police accompagnée de sa fille afin de déposer plainte pénale contre X._ pour les faits susmentionnés. C. X._ forme un recours en matière pénale auprès du Tribunal fédéral contre l'arrêt du 16 octobre 2015. Il conclut principalement à l'annulation de l'arrêt entrepris et à sa réforme en ce sens qu'il est acquitté du chef d'infraction d'actes d'ordre sexuel avec des enfants, que l'Etat de Genève et A._ sont condamnés conjointement et solidairement à lui verser la somme de 26'352 fr., respectivement de 4'860 fr., à titre de réparation du préjudice matériel subi et d'indemnité pour les dépenses occasionnées par l'exercice raisonnable de ses droits de procédure de première instance, respectivement d'appel. Il conclut, pour le surplus, à la confirmation de l'arrêt entrepris. Subsidiairement, il conclut au renvoi de la cause à la Chambre pénale d'appel et de révision de la Cour de justice pour nouvelle décision dans le sens des considérants et, plus subsidiairement encore, à ce qu'il soit acheminé à prouver par toutes voies de droit les faits allégués dans sa requête.