Faits : A. Par jugement du 23 juillet 2014, le Tribunal de police de l'arrondissement de La Broye et du Nord vaudois a libéré X._ du chef de prévention d'abus de la détresse, l'a condamné pour actes d'ordre sexuel avec des enfants et contrainte sexuelle à une peine privative de liberté de huit mois, avec sursis pendant quatre ans, a ordonné un traitement ambulatoire, au titre de règle de conduite durant le délai d'épreuve, auprès d'un organisme public italien agréé par l'Office d'exécution des peines vaudois, a dit qu'il était le débiteur de A.A._ et de B.A._, solidairement entre eux, du montant de 9'711 fr. 90 à titre de dépens pénaux, TVA comprise, et a mis les frais de procédure à sa charge. B. Le 19 février 2015, la Cour d'appel pénale du Tribunal cantonal du canton de Vaud a rejeté l'appel de X._ et admis celui formé par le Ministère public de l'arrondissement du Nord vaudois en ce sens qu'elle a supprimé le sursis à l'exécution de la peine accordé par le tribunal de police, respectivement supprimé la règle de conduite ordonnée. Par arrêt du 26 novembre 2015 (6B_623/2015), la Cour de droit pénal du Tribunal fédéral a partiellement admis le recours déposé par X._ contre ce jugement. La cause a été renvoyée à la cour cantonale afin qu'elle examine la question de savoir si le jugement du 19 septembre 2003 condamnant X._ lui était opposable dans le cadre de l'examen du sursis. Le recours a été rejeté pour le surplus dans la mesure de sa recevabilité. C. Par nouveau jugement du 28 janvier 2016, la Cour d'appel pénale du Tribunal cantonal du canton de Vaud a précisé que dès lors que l'extrait du casier judiciaire délivré le 7 février 2011 mentionnait le jugement du 19 septembre 2003, cette condamnation était opposable à X._ de sorte que la peine privative de liberté de huit mois devait être ferme et la règle de conduite ordonnée supprimée. Elle a ainsi confirmé son jugement du 19 février 2015. D. X._ forme un recours en matière pénale au Tribunal fédéral contre le jugement du 28 janvier 2016, concluant, avec suite de frais et dépens, principalement à la modification du jugement en ce sens qu'il est condamné à une peine privative de liberté de huit mois avec sursis. Les autorités cantonales s'étant déjà prononcées sur la présente affaire dans le cadre du précédent recours déposé par le recourant, le Tribunal fédéral a renoncé à leur demander des déterminations.