Faits : A. Statuant sur opposition à l'ordonnance pénale du 24 janvier 2013, le Juge du district de Sierre a, par jugement du 10 avril 2014, notamment acquitté X._ du chef d'accusation de menaces à l'endroit de son épouse, A._. B. Par jugement du 15 octobre 2015, le Juge de la Cour pénale II du Tribunal cantonal du Valais a admis l'appel formé par A._ contre ce jugement. Il a reconnu X._ coupable de menaces (art. 180 al. 1 et 2 let. a CP) et l'a condamné à un travail d'intérêt général de 40 heures. Il a par ailleurs renoncé à révoquer le sursis accordé par ordonnance pénale du 29 mars 2011. En bref, le Juge de la Cour pénale II a retenu qu'au début du mois d'avril 2011, X._ a exprimé le geste d'égorger sa femme, tout en lui déclarant qu'il entendait faire appel à un tiers pour y procéder. C. X._ forme un recours en matière pénale au Tribunal fédéral. Il conclut à sa libération de l'infraction de menaces et à ce que les frais et dépens soient laissés à la charge de A._.