Faits : A. A._ était propriétaire d'un chat, qu'elle a remis à X._ en décembre 2013 alors qu'elle partait pour cinq semaines en vacances. A son retour elle ne l'a pas repris et l'animal est resté jusqu'à la nuit du 2 au 3 octobre 2014 chez X._, nuit durant laquelle A._, alors en visite chez ce dernier, s'en est emparé. B. Par jugement du 21 juin 2016, le Tribunal de police de l'arrondissement de l'Est vaudois a libéré A._ des chefs d'accusation de vol et de dénonciation calomnieuse. Il l'a condamnée pour vol d'importance mineure à une amende de 2'000 fr., convertible en 20 jours de peine privative de liberté de substitution en cas de non-paiement fautif. Cette autorité a levé le séquestre ordonné le 19 décembre 2014 sur le chat en mains de A._ et l'a condamnée à le restituer à X._, partie plaignante, dans les 48 h dès jugement définitif et exécutoire. A._ a été astreinte à verser à X._ 500 fr. à titre d'indemnité pour tort moral et 12'000 fr. pour ses frais de défense. Elle a également été condamnée à assumer les frais de justice arrêtés à 3'225 francs. C. Par jugement du 2 novembre 2016, le Président de la Cour d'appel pénale du Tribunal cantonal du canton de Vaud a partiellement admis l'appel formé par A._ contre le jugement précité, l'a acquittée de tous les chefs d'accusation pesant contre elle et a levé le séquestre sur l'animal en sa faveur. Il a accordé à A._, à charge de l'Etat, une indemnité pour l'exercice raisonnable de ses droits de procédure, à hauteur de 2'754 fr. en première instance et de 1'533 fr. 60 en seconde instance. Il a pour le surplus mis les frais de la cause de première instance à charge de l'Etat, et de seconde instance à charge de X._ pour 3⁄4, le solde étant laissé à la charge de l'Etat. D. X._ forme un recours en matière pénale auprès du Tribunal fédéral contre le jugement du 2 novembre 2016. Il conclut, avec suite de frais et dépens, à sa réforme en ce sens que l'appel est rejeté et le jugement du 21 juin 2016 confirmé, subsidiairement à son annulation et au renvoi de la cause à l'autorité précédente pour nouvelle décision. Il requiert la mise en oeuvre de mesures provisionnelles. E. Par ordonnance du 23 février 2017, le Président de la Cour de droit pénal du Tribunal fédéral a interprété les mesures provisionnelles requises comme une demande d'effet suspensif et y a agréé avec pour effet notamment le maintien du séquestre prononcé le 19 décembre 2014 sur l'animal. F. Invités à se déterminer sur le recours, la Cour d'appel pénale et le ministère public y ont renoncé. L'intimée a déposé une réponse, concluant, avec suite de frais et dépens, au rejet du recours. Le recourant a ensuite formulé des observations, qui ont été communiquées aux autorités précitées et à l'intimée.