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.

Considérant en droit :
1.
Le recourant soutient que la cour cantonale aurait violé l'<ref-law>.
1.1. L'inscription des jugements qui prononcent une peine privative de liberté avec sursis doit être éliminée d'office du casier judiciaire après dix ans (<ref-law>). Ce délai court du jour où le jugement est exécutoire (<ref-law>). Aux termes de l'<ref-law>, l'inscription ne doit pas pouvoir être reconstituée après son élimination; le jugement éliminé ne peut plus être opposé à la personne concernée. Cela signifie qu'il ne peut plus avoir de conséquences juridiques (<ref-ruling> consid. 2.3 p. 91). Il ressort ainsi du texte de l'<ref-law> que l'inopposabilité est un effet de l'élimination de l'inscription, c'est-à-dire d'un acte de l'autorité administrative chargée de la tenue du casier judiciaire, et non un effet direct de l'écoulement du temps (arrêt 6B_53/2010 du 22 avril 2010 consid. 1.1; en ce sens: Message du 21 septembre 1998 concernant la modification du code pénal suisse et du code pénal militaire ainsi qu'une loi fédérale régissant la condition pénale des mineurs, FF 1999 1975 s. ch. 236.5). Pour vérifier qu'un jugement ne soit pas inopposable à un prévenu, il est donc nécessaire de disposer d'un extrait du casier judiciaire (arrêt 6B_53/2010 précité consid. 1.1).
1.2. Conformément à l'<ref-law>, la juridiction d'appel jouit d'un plein pouvoir d'examen sur tous les points attaqués du jugement. Cette disposition consacre, dans son principe, le caractère complet de l'appel, voie de droit ordinaire, qui aboutit, dans la règle, à un nouveau jugement remplaçant l'ancien (<ref-law>). Il reste que la procédure de recours au sens large ( Rechtsmittel par opposition à Beschwerde) se fonde sur les preuves administrées pendant la procédure préliminaire et la procédure de première instance (<ref-law>), selon le principe de l'immédiateté restreinte de l'administration des preuves qui prévaut déjà en première instance (cf. art. 343 et 349 CPP a contrario). Mais l'autorité de recours n'en administre pas moins, d'office ou à la demande d'une partie, les preuves complémentaires nécessaires au traitement du recours (<ref-law>).
1.3. La cour cantonale a retenu que le dossier de la cause contenait un extrait du casier judiciaire du recourant et que cet extrait était joint, « comme dans tous les dossiers, à la deuxième expédition du jugement de première instance du 23 juillet 2014 se trouvant dans le dossier ». L'extrait du casier judiciaire ayant été délivré le 7 février 2011, soit moins de huit ans après le prononcé du jugement du 19 septembre 2003 et avant l'échéance du délai de dix ans prévu par l'<ref-law>, il était opposable au recourant et l'hypothèse de reconstitution prohibée à l'<ref-law> n'était pas réalisée dans le cas particulier, de sorte qu'elle a refusé de lui octroyer le sursis.
1.4. Certes, l'extrait du casier judiciaire établi le 7 février 2011 - qui a été adressé à la cour de céans, à sa demande, par l'autorité précédente par courrier électronique du 23 juin 2016, dès lors qu'il ne figurait pas au dossier cantonal lui ayant été transmis - fait état du jugement rendu le 19 septembre 2003 par le Tribunal correctionnel de Neuchâtel. La cour cantonale perd toutefois de vue qu'elle jouit d'un plein pouvoir d'examen en fait et en droit sur tous les points attaqués du jugement et qu'il lui appartient, dès lors, de rendre un nouveau jugement se substituant à celui de première instance (cf. <ref-law>) s'agissant de la question du sursis. Pour ce faire, il lui incombe d'administrer d'office les preuves complémentaires nécessaires au traitement de l'appel, en particulier de s'enquérir d'un extrait du casier judiciaire du recourant actualisé, afin de déterminer, cas échéant, si au moment où elle statue, l'inscription du jugement du 19 septembre 2003 a été éliminée dans l'intervalle, respectivement à quelle date, et d'en tirer les conséquences juridiques quant à l'octroi ou non du sursis. L'arrêt de renvoi 6B_623/2015 lui imposait d'éclaircir l'aspect d'élimination de l'inscription au moment où elle statuait, ce qu'elle a omis de faire.
2.
Le recours doit, en conséquence, être admis, le jugement attaqué annulé en ce qui concerne le refus du sursis et la cause renvoyée à la cour cantonale pour qu'elle instruise dans le sens du considérant précité et statue à nouveau sur cette question.
Le recourant obtenant gain de cause, il ne sera pas perçu de frais (<ref-law>). Il a droit à des dépens, à la charge du canton de Vaud (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis, le jugement attaqué est annulé et la cause est renvoyée à la cour cantonale pour nouvelle décision.
2.
Il n'est pas perçu de frais judiciaires.
3.
Le canton de Vaud versera au recourant le montant de 3'000 fr. à titre de dépens pour la procédure devant le Tribunal fédéral.
4.
Le présent arrêt est communiqué aux parties et à la Cour d'appel pénale du Tribunal cantonal du canton de Vaud.
Lausanne, le 29 juin 2016
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
La Greffière : Nasel