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._.

Considérant en droit :
1.
Le recours s'ouvre sur une présentation des faits sans que le grief d'arbitraire ne soit soulevé. On n'examinera les points ainsi exposés qu'autant que le recourant développe, dans la suite de son mémoire, des griefs répondant aux exigences de motivation des art. 42 al. 2 et 106 al. 2 LTF.
2.
Le recourant conteste les faits retenus par la cour cantonale et invoque la présomption d'innocence.
2.1. Dans le recours en matière pénale, les constatations de fait de la décision entreprise lient le Tribunal fédéral (<ref-law>). Le recourant ne peut critiquer ceux-ci que s'ils ont été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 2.3 p. 266) - ou en violation du droit au sens de l'<ref-law> (<ref-law>). En matière d'appréciation des preuves et d'établissement des faits, il y a arbitraire lorsque l'autorité ne prend pas en compte, sans aucune raison sérieuse, un élément de preuve propre à modifier la décision, lorsqu'elle se trompe manifestement sur son sens et sa portée, ou encore lorsque, en se fondant sur les éléments recueillis, elle en tire des constatations insoutenables (<ref-ruling> consid. 2.3 p. 266). Au stade de l'appréciation des preuves, le grief d'arbitraire se confond avec celui déduit de la violation du principe in dubio pro reo (art. 32 Cst.; art. 6 par. 2 CEDH; <ref-ruling> consid. 7 p. 82; <ref-ruling> consid. 2a p. 88). Comme principe présidant à l'appréciation des preuves, la présomption d'innocence est violée si le juge du fond se déclare convaincu de faits défavorables à l'accusé sur lesquels, compte tenu des éléments de preuve qui lui sont soumis, il aurait au contraire dû, objectivement, éprouver des doutes (<ref-ruling> consid. 7 p. 82; <ref-ruling> consid. 2a p. 41). En tant que règle relative au fardeau de la preuve, la présomption d'innocence signifie que toute personne prévenue d'une infraction pénale doit être présumée innocente jusqu'à ce que sa culpabilité soit légalement établie et, partant, qu'il appartient à l'accusation de prouver la culpabilité de l'intéressé (ATF <ref-ruling> consid. 2a p. 41).
Le Tribunal fédéral n'examine la violation de droits fondamentaux que si ce moyen est invoqué et motivé par le recourant (<ref-law>), c'est-à-dire s'il a été expressément soulevé et exposé de manière claire et détaillée. Les critiques de nature appellatoire sont irrecevables (<ref-ruling> consid. 2.3 p. 266).
2.2. Le recourant soutient, en substance, qu'il était arbitraire de retenir qu'il avait menacé l'intimée. Il conteste que ses déclarations du 18 août 2011 puissent être considérées comme des aveux en rapport avec les faits faisant l'objet de la présente procédure; il n'avait en effet reconnu que les menaces du 1er juillet 2010, pour lesquelles il avait déjà été condamné par ordonnance pénale du 29 avril 2011. Même dans le cas contraire, ses rétractations du 9 avril 2013 devaient emporter la conviction du juge. Par ailleurs, les accusations très générales et peu détaillées de l'intimée n'étaient pas crédibles. La cour cantonale s'était en outre fondée sur des faits non prouvés pour en déduire que son comportement et son tempérament étaient compatibles avec les faits de la cause.
2.3. De manière générale, le recourant rediscute les éléments de preuve pris en considération par la cour cantonale, à laquelle il oppose, pour l'essentiel, sa propre appréciation. Une telle démarche, appellatoire, n'est pas admissible dans le recours en matière pénale (consid. 2.1 supra). Ce nonobstant, même à supposer que ses griefs soient recevables, ils sont infondés pour les motifs qui suivent.
2.3.1. Selon le procès-verbal d'audition du recourant du 18 août 2011, la police a posé au recourant la question suivante: " Connaissance vous est donnée des griefs exprimés par votre épouse dans sa plainte du 25.08.2011; veuillez-vous expliquer (sic) ? ". Comme le relève le recourant, la date mentionnée est fausse: en effet, la plainte de l'intimée a été reçue le 25.07.2011 et non le 25.08.2011 (dossier n°5). Il s'agit vraisemblablement d'une erreur dans la transcription du procès-verbal, la date erronée se situant dans l'avenir par rapport au jour de l'audition du recourant. En tous les cas, le recourant pouvait comprendre qu'il s'agissait d'une plainte déposée récemment. Autant qu'il soutient que seuls les " griefs ", et non les " faits " de la plainte lui auraient été exposés, le recourant n'établit pas qu'il ne lui aurait pas été donné une connaissance suffisante de la plainte, lui permettant en particulier d'identifier les actes qui lui étaient reprochés dans ce cadre.
Par ailleurs, la cour cantonale a relevé à juste titre que si le recourant avait pensé qu'il avait été convoqué par la police pour répondre une nouvelle fois d'agissements pour lesquels il avait été condamné cinq mois plus tôt - comme il l'a soutenu lors de son audition du 9 avril 2013 - il n'aurait certainement pas manqué de le signaler immédiatement. Contrairement à ce que soutient le recourant, cette appréciation ne consacre pas un renversement du fardeau de la preuve; en effet, elle ne repose pas sur l'absence de démonstration de son innocence par le recourant, mais sur l'appréciation des preuves disponibles.
Or, loin de rétorquer qu'il avait déjà été condamné pour les faits sur lesquels il était interrogé, l'intéressé a déclaré, le 18 août 2011: " Je reconnais que lors de nos disputes de couple, j'ai dû prononcer des menaces de mort ". A raison, la cour cantonale a retenu que l'emploi du pluriel excluait qu'il n'eût en tête que les faits du 1er juillet 2010, objet de l'ordonnance pénale du 29 mars 2011. Enfin, dans la mesure où le recourant situe sa séparation définitive d'avec l'intimée le 10 avril 2011, les termes " disputes de couple " peuvent tout à fait se rapporter aux disputes intervenues début avril 2011, soit au moment de la commission de l'infraction reprochée dans la présente cause.
La cour cantonale pouvait ainsi retenir sans arbitraire que le recourant avait avoué avoir proféré des menaces à l'endroit de son épouse en avril 2011 et que ses rétractations intervenues le 9 avril 2013 n'étaient pas convaincantes, ce d'autant qu'il a encore modifié sa version des faits par la suite en évoquant des injures plutôt que des menaces.
2.3.2. Contrairement à ce qu'affirme le recourant, les déclarations de la victime, entendue comme témoin ou personne appelée à donner des renseignements, constituent un élément de preuve. Le juge doit, dans l'évaluation globale de l'ensemble des éléments probatoires rassemblés au dossier, les apprécier librement (arrêts 6B_716/2010 du 15 novembre 2010 consid. 1.3; 6B_360/2008 du 12 novembre 2008 consid. 4.3). A supposer que la plainte de A._ doive être qualifiée de vague comme le soutient le recourant, on ne voit pas encore en quoi il faudrait en déduire que l'intimée n'est pas crédible, attendu qu'elle a précisé les reproches adressés à son époux lors de ses différentes auditions. La cour cantonale a de surcroît relevé que ses déclarations étaient demeurées constantes, ce que le recourant ne conteste pas. Le fait que les enfants du couple aient choisi de vivre avec leur père plutôt qu'avec leur mère, ou encore que le comportement de celle-ci ne soit - prétendument - pas dénué de tout reproche ne présente pas de rapport direct avec les faits dénoncés, partant, n'entame pas la crédibilité des déclarations de l'intimée. Par ailleurs, que celle-ci n'ait pas affirmé de manière claire avoir peur de son mari ne rend pas sa version des faits moins plausible; au contraire, la mesure de ses propos, de même que l'absence de toute exagération dans ses accusations, constituaient des indices pertinents dans l'appréciation de sa crédibilité. Fondée sur ce qui précède, la cour cantonale pouvait, sans arbitraire, retenir les déclarations de l'intimée pour forger sa conviction.
2.3.3. Enfin, l'appréciation de la cour cantonale sur la compatibilité du tempérament et du comportement du recourant avec les propos litigieux n'est pas insoutenable dans la mesure où elle se fonde sur des faits qui ont fait l'objet d'une ordonnance pénale entrée en force (menacer l'intimée de la " buter " en lui mettant la main sur le visage pour qu'elle se taise) ou qui ont été admis par le recourant (jeter l'argent de la pension alimentaire à la figure de l'intimée, dossier n°20; stationner avec son véhicule derrière celui de l'intimée avant de la suivre, dossier n°34).
2.3.4. Il s'ensuit que la cour cantonale n'est pas tombée dans l'arbitraire en retenant, à l'issue de son appréciation des preuves, que le recourant avait menacé de mort l'intimée en mimant le geste consistant à lui trancher la gorge et en déclarant qu'il chargerait quelqu'un de s'en occuper. Le grief est rejeté dans la mesure de sa recevabilité.
3.
Le recourant invoque une violation de l'<ref-law> au motif que l'ordonnance pénale tenant lieu d'acte d'accusation manquerait de précision dès lors que tant le lieu, la date, que l'heure de la commission des menaces ou encore le type de menaces retenues à sa charge feraient défaut.
3.1. Aux termes de l'<ref-law>, une infraction ne peut faire l'objet d'un jugement que si le ministère public a déposé auprès du tribunal compétent un acte d'accusation dirigé contre une personne déterminée sur la base de faits précisément décrits. L'<ref-law> exige que l'acte d'accusation désigne, notamment, le plus brièvement possible, mais avec précision, les actes reprochés au prévenu, le lieu, la date et l'heure de leur commission ainsi que leurs conséquences et le mode de procéder de l'auteur (let. f) de même que les infractions réalisées et les dispositions légales applicables de l'avis du ministère public (let. g). Des imprécisions relatives au lieu ou à la date sont sans portée, dans la mesure où le prévenu ne peut avoir de doute sur le comportement qui lui est reproché (arrêt 6B_907/2013 du 3 octobre 2014 consid. 1.5).
En vertu de l'<ref-law>, lorsque le ministère public décide, malgré une opposition, de maintenir l'ordonnance pénale, le ministère public transmet sans retard le dossier au tribunal de première instance en vue des débats. L'ordonnance pénale tient lieu d'acte d'accusation.
3.2. Dans le cas d'espèce, l'ordonnance pénale situe les faits dans le " courant du mois d'avril 2011" et les localise au domicile conjugal, soit à Sierre. Le ministère public a spécifié que le recourant reconnaissait avoir " proféré diverses menaces de mort " à l'encontre de sa femme. Il a exposé plus précisément qu'il avait " notamment fait le geste de lui trancher la gorge tout en précisant que pour cela il allait engager quelqu'un ".
3.3. Le recourant était en mesure de préparer efficacement sa défense sur la base de cet acte d'accusation. En particulier, il pouvait identifier tant le lieu que la période correspondant à la commission de l'infraction. En outre, la menace qui a valu au recourant sa condamnation est précisément décrite dans l'acte d'accusation. Le recourant ne soutient pas, d'ailleurs, qu'il aurait eu des doutes sur le comportement qui lui était reproché. Ses propos tenus après avoir fait opposition à l'ordonnance pénale et lors des débats de première instance, relevés par la cour cantonale, confirment, au besoin, sa parfaite compréhension des reproches qui lui étaient adressés et qui ont entraîné sa condamnation.
Mal fondé, le grief soulevé est rejeté.
4.
Le recours doit ainsi être rejeté dans la mesure de sa recevabilité. Le recourant supportera les frais judiciaires (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté dans la mesure où il est recevable.
2.
Les frais judiciaires, arrêtés à 2000 fr., sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué aux parties et au Tribunal cantonal du canton du Valais, Le Juge de la Cour pénale II.
Lausanne, le 19 juillet 2016
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
La Juge présidant : Jacquemoud-Rossari
La Greffière : Musy