Faits : A. Par jugement du 4 août 2015, le Tribunal de police de l'arrondissement de U._ a déclaré X._ coupable de gestion déloyale et l'a condamné à une peine de 90 jours-amende à 50 fr. le jour avec sursis pendant deux ans. Il l'a également condamné à verser à A._ une indemnité de dépens de 13'106 fr. au sens de l'art. 433 CPP. Il a mis les frais de la procédure à la charge du prévenu condamné. B. Par jugement du 2 février 2016, la Cour d'appel pénale du Tribunal cantonal du canton de Vaud a rejeté le recours de X._. Il l'a condamné aux frais de la procédure d'appel et à verser à A._ une indemnité de dépens pénaux de 3'240 francs. C. L'autorité précédente a retenu les faits suivants : Le 3 octobre 2011, X._, agissant pour le compte de B._ Sàrl dont il était associé-gérant, et A._, propriétaire économique de C._ SA, ont signé un contrat de courtage portant sur la vente du fonds de commerce de l'institut de beauté « C._ » installé dans des locaux loués à U._ et exploité par C._ SA. Le prix de vente souhaité était de 55'000 francs. Une commission forfaitaire en faveur du courtier de 10'000 fr. était prévue jusqu'à un prix de vente de 100'000 francs. Le 10 novembre 2011, A._ a vendu la totalité des actions de C._ SA à X._ pour le montant de 1 franc et, le même jour, ce dernier est devenu administrateur unique de la société. Le 6 mars 2012, A._ a informé X._ qu'elle consentait à baisser le prix de vente de C._ SA à 35'000 francs. Le 13 mars 2012, X._ a vendu la totalité du matériel qui se trouvait dans les locaux loués par C._ SA pour le prix de 10'000 fr., somme qu'il a versée sur le compte de B._ Sàrl, dont la faillite a été prononcée le 4 juin 2014. Le montant en question a donc été définitivement perdu. L'instruction n'a pas permis de déterminer la valeur des actifs de C._ SA. Concernant la vente des actions de cette société, X._ a admis qu'elle avait eu lieu à titre fiduciaire et que le contrat de courtage avait gardé sa validité après cette vente. D. X._ interjette un recours en matière pénale au Tribunal fédéral contre le jugement du 2 février 2016. Principalement et en réformation du jugement cantonal, il conclut, avec suite de frais et dépens, à son acquittement pour la prévention de gestion déloyale et à sa libération du paiement de toutes les indemnités de dépens pénaux allouées à A._ ainsi que du paiement des frais judiciaires pour les deux instances. Il réclame pour lui une indemnité de dépens pénaux de 17'000 francs. Subsidiairement, il conclut à l'annulation du jugement cantonal et au renvoi du dossier pour nouvelle décision à l'autorité précédente. E. Appelée à se prononcer, l'autorité précédente a renoncé à se déterminer et a renvoyé aux considérants de sa décision. L'intimée a pris position en concluant au rejet du recours et à la confirmation du jugement cantonal. Le recourant s'est déterminé sur cette écriture. L'intimée a encore adressé des déterminations.