Faits :
A.
X._, ressortissant macédonien né en 1968, est entré une première fois en Suisse en 1988 et a été mis au bénéfice d'un permis de saisonnier. Ce permis a été régulièrement prolongé jusqu'au 31 janvier 1995. En février 1996, l'intéressé a regagné son pays, avant de revenir illégalement en Suisse à plusieurs reprises. Ayant obtenu un visa en vue de se marier, X._ est entré en Suisse le 28 mai 2000. Le 27 juillet 2000, il a obtenu une autorisation de séjour et le 28 juillet 2000, il a épousé une ressortissante helvétique.
Le 3 septembre 2007, l'intéressé a rempli une demande de délivrance d'une autorisation d'établissement, à laquelle étaient notamment annexés un rapport du 24 août 2007 mentionnant qu'il n'avait pas d'enfants suivant l'école de façon permanente depuis leur arrivée en Suisse (<ref-law>), ainsi qu'une déclaration de ménage commun signée par les époux. Le 7 septembre 2007, il a obtenu l'autorisation d'établissement demandée.
Les époux se sont séparés au mois de novembre 2008. Ils ont divorcé le 16 août 2011. Le 2 novembre 2012, l'intéressé a épousé une compatriote dans son pays d'origine avec laquelle il avait déjà deux enfants, nésen janvier 2001 et en septembre 2010. Le 20 mars 2013, il a déposé une demande de regroupement familial en faveur de sa femme et de ses deux enfants.
B.
Par décision du 25 juillet 2013, le Service de la population et des migrations du canton du Valais (ci-après: le Service cantonal) a révoqué l'autorisation d'établissement accordée à X._, ordonné son renvoi de Suisse et "classé sans suite" les demandes de regroupement familial. Le 26 août 2013, l'intéressé a interjeté recours contre cette décision auprès du Conseil d'Etat du canton du Valais. Celui-ci a rejeté le recours par décision du 5 novembre 2014. X._ a contesté ce prononcé devant la Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal) le 5 janvier 2015.
Par arrêt du 24 juin 2015, le Tribunal cantonal a rejeté le recours de l'intéressé. Il a jugé en substance qu'un faisceau d'indices démontrait que ce dernier avait volontairement tu être le père d'un enfant né d'une relation entretenue en Macédoine et que la révocation de son autorisation d'établissement se justifiait pour cette raison.
C.
Agissant par la voie du recours en matière de droit public et celle, subsidiaire, du recours constitutionnel, X._ demande au Tribunal fédéral, sous suite de frais et dépens, outre l'effet suspensif, l'annulation de l'arrêt du 24 juin 2015 du Tribunal cantonal et le renvoi de la cause au Service cantonal, afin que celui-ci statue sur la demande de regroupement familial. Il se plaint d'arbitraire dans l'appréciation des preuves et de violation du droit fédéral.
Par ordonnance du 28 août 2015, le Président de la IIe Cour de droit public du Tribunal fédéral a admis la demande d'effet suspensif.
Le Tribunal cantonal et le Secrétariat d'Etat aux migrations concluent tous deux au rejet du recours, sans présenter de déterminations. Le Service cantonal ne s'est pas déterminé. Le Conseil d'Etat du canton du Valais a produit sa prise de position hors délai.

Considérant en droit :
1.
1.1. D'après l'art. 83 let. c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions en matière de droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral ni le droit international ne donnent droit. Il est recevable contre les décisions révoquant, comme en l'espèce, une autorisation d'établissement parce qu'il existe en principe un droit au maintien de cette autorisation (<ref-ruling> consid. 1.2.1 p. 4; arrêt 2C_789/2014 du 20 février 2015 consid. 1). Il est en outre également recevable en tant qu'il a trait au regroupement familial, le recourant, dans la mesure où son autorisation d'établissement venait à ne pas être révoquée, pourrait faire bénéficier sa famille d'un droit fondé sur l'art. 43 al. 1 et 3 LEtr (cf. arrêt 2C_536/2013 du 30 décembre 2013 consid. 1, non publié in <ref-ruling>). La présente cause ne tombe ainsi pas sous le coup de l'art. 83 let. c ch. 2 LTF, ni d'aucune autre clause d'irrecevabilité figurant à l'<ref-law>. Partant, la voie du recours en matière de droit public est ouverte. Le recours constitutionnel subsidiaire est irrecevable.
1.2. Au surplus, déposé en temps utile (art. 46 al. 1 let. b et 100 al. 1 LTF) et dans les formes prescrites par la loi (<ref-law>), par le destinataire de l'arrêt attaqué qui a un intérêt digne de protection à son annulation ou à sa modification (<ref-law>), le présent recours, dirigé contre une décision finale (<ref-law>) rendue par une autorité cantonale supérieure de dernière instance (art. 86 al. 1 let. d et al. 2 LTF) dans une cause de droit public (<ref-law>), est recevable.
2.
Le recourant fait en premier lieu valoir que l'autorité précédente a apprécié les preuves à sa disposition de manière arbitraire. Il conteste avoir eu connaissance de l'existence de son fils, né en 2001, lors de sa demande d'autorisation d'établissement. Il nie en outre avoir gardé des contacts avec la mère de ses enfants alors qu'il était marié avec sa première épouse.
2.1. L'appréciation des preuves est arbitraire ou manifestement inexacte au sens de l'<ref-law> lorsqu'elle est en contradiction avec le dossier, ou contraire au sens de la justice et de l'équité ou lorsque l'autorité ne tient pas compte, sans raison sérieuse, d'un élément propre à modifier la décision, se trompe sur le sens et la portée de celui-ci ou, se fondant sur les éléments recueillis, en tire des constatations insoutenables (cf. <ref-ruling> consid. 4.2 p. 233 s.; <ref-ruling> consid. 4.3 p. 62 et les références). Il appartient à la partie recourante de démontrer le caractère arbitraire par une argumentation répondant aux exigences accrues de motivation de l'<ref-law> (<ref-ruling> consid. 4.1.2 p. 62; <ref-ruling> consid. 1.4.3 p. 254 s.). En particulier, le Tribunal fédéral n'entre pas en matière sur des critiques de type appellatoire portant sur l'état de fait ou l'appréciation des preuves (<ref-ruling> consid. 10.1 p. 444 et les arrêts cités).
2.2. Dans son arrêt, le Tribunal cantonal a considéré que les éléments au dossier permettaient de retenir que le recourant, contrairement à ce qu'il affirme, avait connaissance de l'existence de son fils avant 2007, soit avant sa demande d'autorisation d'établissement. Il ressort de l'appréciation des faits effectuée par les juges cantonaux qu'il existe des contradictions entre les déclarations du recourant et celles de son ex-épouse helvétique quant à la durée et la fréquence des séjours de celui-ci dans son pays d'origine. Le Tribunal cantonal a également relevé que le chef de mission auprès de l'Ambassade de Suisse à Skopje, qui a entendu l'épouse actuelle du recourant, avait considéré que la présentation des faits dressée par cette dernière était incompatible avec les coutumes prévalant en Macédoine. De plus, celle-ci avait menti à ce représentant diplomatique au sujet de son passeport et varié sur les dates et périodes durant lesquelles elle était venue en Suisse, ce qui rendait ses déclarations en faveur du recourant peu crédibles. L'autorité précédente a également relevé que le recourant vient d'un village d'environ 4'000 habitants dans lequel vivent ses parents. Ce village n'est éloigné que de quelques kilomètres du village, de grandeur semblable, dans lequel habite la mère des enfants du recourant. Compte tenu de ces éléments de fait, et en particulier des nombreux voyages de l'intéressé dans son pays d'origine, il n'est pas arbitraire de considérer que le recourant devait avoir connaissance de la naissance de son premier enfant au moins avant sa demande d'autorisation d'établissement en 2007, année durant laquelle cet enfant a fêté ses six ans.
A cela s'ajoute que le recourant a conçu son premier enfant en Macédoine, alors qu'il était déjà fiancé avec son ex-épouse et que les démarches en vue de sa venue en Suisse étaient déjà bien avancées. Il a de plus conçu son second enfant alors qu'il était toujours marié avec sa première femme et a épousé la seconde à peine plus d'une année après son divorce. Il n'est ainsi pas non plus arbitraire de considérer que l'épouse actuelle de l'intéressé devait avoir ressenti "la tentation de confier au recourant qu'il était père, ce d'autant plus que cette naissance a dû entraîner des besoins financiers plus importants". Le fait que le recourant ait régulièrement envoyé de l'ar gent en Macédoine permet également de considérer comme exempt d'arbitraire l'appréciation des faits effectuée par le Tribunal cantonal. Il est par conséquent soutenable de considérer, comme le fait l'autorité précédente, que la relation que le recourant a entretenue avec son épouse actuelle présente un caractère solide et durable et qu'il a gardé contact avec elle durant son mariage avec son épouse suisse.
Contrairement à ce que fait valoir le recourant, l'autorité précédente ne s'est pas uniquement fondée sur les déclarations de l'ex-épouse du recourant et du chef de mission de l'Ambassade de Suisse pour considérer qu'il avait connaissance de l'existence de son premier enfant, mais sur l'ensemble des faits pertinents figurant au dossier. Dans ces conditions, il convient d'écarter le grief portant sur une appréciation arbitraire des faits. Le Tribunal fédéral vérifiera donc la correcte application du droit sur la seule base des faits retenus par l'autorité précédente.
3.
3.1. A teneur de l'art. 63 al. 2 LEtr, l'autorisation d'établissement d'un étranger qui séjourne en Suisse légalement et sans interruption depuis plus de quinze ans ne peut être révoquée que pour les motifs mentionnés aux art. 62 let. b et 63 al. 1 let. b LEtr. Le respect de cette durée se vérifie au jour du prononcé de la décision de révocation de l'autorisation d'établissement par l'autorité de première instance (<ref-ruling> consid. 4.2 p. 12). Pour les étrangers qui séjournent légalement en Suisse depuis moins de quinze ans, l'art. 63 al. 1 let. a LEtr prévoit que l'autorisation d'établissement peut notamment être révoquée aux conditions de l'art. 62 let. a LEtr, c'est-à-dire si l'étranger ou son représentant légal a fait de fausses déclarations (première alternative de l'art. 62 let. a LEtr) ou a dissimulé des faits essentiels durant la procédure d'autorisation (seconde alternative de l'art. 62 let. a LEtr). Ainsi, lorsque l'autorité pose des questions à l'étranger, celui-ci doit y répondre conformément à la vérité. Les fausses déclarations, qui portent sur des élément déterminants pour l'octroi de l'autorisation de séjour ou d'établissement, conduisent à la révocation de celle-ci. Il ne doit toutefois pas être établi que l'autorisation aurait avec certitude été refusée si l'autorité avait obtenu une information correcte. Quant à la dissimulation de faits essentiels, au même titre que pour les fausses déclarations (cf. <ref-ruling> consid. 3b p. 475 s.; ANDREAS ZÜND, in BERNHARD EHRENZELLER [éd.], Aktuelle Fragen des schweizerischen Ausländerrechts, volume 4, 2001, p. 141; ZÜND/ARQUINT HILL, in UEBERSAX ET AL. [éd.], Ausländerrecht, 2e éd. 2009, n° 8.27; MARC SPESCHA, in SPESCHA ET AL. [éd.], Migrationsrecht, 4e éd. 2015, n° 3 ad art. 62 LEtr), il faut que l'étranger ait la volonté de tromper l'autorité (arrêts 2C_736/2015 du 22 février 2016 consid. 3.2.1; 2C_403/2011 du 2 décembre 2011 consid. 3.3.3). Cela est notamment le cas lorsqu'il cherche à provoquer, respectivement à maintenir, une fausse apparence sur un fait essentiel (arrêts 2C_403/2011 précité consid. 3.3.3; 2C_595/2011 du 24 janvier 2012 consid. 3.4; 2C_726/2011 du 20 août 2012 consid. 3.1.1).
3.2. De l'avis du Tribunal cantonal, citant l'arrêt 2C_299/2012 du 6 août 2012 consid. 4.1 (renvoyant lui-même aux arrêts 2C_595/2011 du 24 janvier 2012 consid. 3.3, 2C_552/2011 du 15 mars 2012 consid. 4.3 et 2C_403/2011 du 2 décembre 2011 consid. 3.3.2 et les arrêts cités), il y a déjà dissimulation d'un fait essentiel au sens de l'art. 62 let. a en relation avec l'art. 63 al. 1 let. a LEtr, lorsque l'étranger tait l'existence d'un conjoint ou d'un enfant. Cette jurisprudence n'est toutefois pas assez nuancée et elle doit être précisée.
L'étranger est tenu de collaborer à la constatation des faits et en particulier de fournir des indications exactes et complètes sur les éléments déterminants pour la réglementation du séjour (art. 90 al. 1 let. a LEtr; arrêt 2C_161/2013 du 3 septembre 2013 consid. 2.2.1). Toutefois, il appartient en premier lieu à l'autorité de poser les questions appropriées à l'étranger (cf. arrêts 2C_113/2016 du 29 février 2016 consid. 2.2; 2C_988/2014 du 1er septembre 2015 consid. 2.2; ANDREAS ZÜND, op.cit., p. 141; ZÜND/ARQUINT HILL, op. cit., n° 8.27). Il ne saurait être reproché à ce dernier de ne pas avoir de lui-même indiqué un élément de fait qu'il ne devait pas considérer comme étant déterminant pour l'octroi de son autorisation. Ainsi, en l'absence de question précise de l'autorité chargée de l'instruction, on ne peut critiquer l'étranger de ne pas avoir annoncé l'existence d'un enfant né d'une autre union que celle fondant l'autorisation de séjour ou d'établissement. Un tel élément n'a en effet pas d'incidence essentielle sur le droit d'obtenir une autorisation, car il ne peut pas être présumé que son existence conduirait vraisemblablement à reconnaître un caractère fictif à l'union donnant droit à une autorisation en Suisse. Il en va en revanche différemment de l'absence d'indications quant à l'existence d'une liaison parallèle. En ne mentionnant pas qu'il entretient une relation durable avec une autre personne, l'étranger cherche à tromper l'autorité sur le caractère stable de sa relation vécue en Suisse avec la personne lui donnant le droit d'obtenir une autorisation de séjour ou d'établissement, conformément aux art. 42 et 43 LEtr. Il provoque ou maintient ainsi une fausse apparence de monogamie. La dissimulation d'une relation parallèle conduit donc à la révocation de l'autorisation, en application de l'art. 62 let. a LEtr (par renvoi de l'art. 63 al. 1 let. a LEtr s'il est question d'autorisation d'établissement).
4.
4.1. En l'occurrence, la décision de révocation de l'autorisation d'établissement du recourant a été prononcée par le Service cantonal le 25 juillet 2013, c'est-à-dire un peu plus de treize ans après que le recourant était arrivé en Suisse. L'art. 63 al. 2 LEtr ne trouve donc pas application au cas d'espèce et il convient d'examiner si les conditions de l'art. 62 let. a en relation avec l'art. 63 al. 1 let. a LEtr sont remplies. Contrairement à ce que le recourant tente d'invoquer, le fait qu'il ait déjà séjourné légalement en Suisse entre la fin des années 80 et février 1996 n'y change rien, puisque, comme l'indique l'art. 63 al. 2 LEtr, seuls comptent les séjours ininterrompus.
4.2. Il ressort des faits retenus par l'autorité précédente qu'entre 1996 et 1997, le recourant a tenté à plusieurs reprises de pénétrer sur le territoire helvétique, avant de se marier avec une ressortissante suisse. Après un peu plus de sept ans de mariage, le recourant a déposé une demande d'autorisation d'établissement. Le couple s'est séparé environ une année plus tard et a divorcé un peu moins de deux ans après cette séparation. Les époux n'ont pas eu d'enfants. Durant cette union, le recourant a entretenu une relation avec la mère de son fils, en Macédoine. Celui-ci a été conçu alors que le recourant préparait son mariage en Suisse. A la date du mariage, sa compatriote était enceinte de trois mois. Avant que les époux n'aient divorcé, le recourant a conçu un deuxième enfant avec la mère de son premier fils. Le 2 novembre 2012, soit à peine plus d'une année après son divorce en Suisse, le recourant a épousé sa compatriote. Dans la foulée, soit moins de cinq mois après son second mariage, il a déposé une demande de regroupement familial pour sa femme et ses deux enfants.
4.3. Contrairement à ce qu'a retenu l'autorité précédente, les autorités chargées de délivrer au recourant son autorisation d'établissement en 2007 ne lui ont pas demandé s'il avait des enfants. Le rapport joint par le recourant à la demande d'autorisation d'établissement ne concernait que l'éventuelle scolarisation d'enfants en Suisse. En joignant ce formulaire à sa demande, sans autre remarque, le recourant n'a pas fait de fausses déclarations, même s'il a tu l'existence de son fils. Or, comme on l'a vu précédemment, la seule dissimulation d'un enfant sans question précise de l'autorité à ce sujet ne constitue pas un cas de révocation de l'autorisation d'établissement. En revanche, comme cela a été retenu par le Tribunal cantonal, le recourant a entretenu durant toute sa relation avec sa femme en Suisse, une relation parallèle avec une compatriote en Macédoine qu'il a fini par épouser. Dissimuler une telle relation constitue un cas de révocation de l'autorisation d'établissement, si bien que l'arrêt entrepris doit être confirmé sur ce point et le grief de violation de l'art. 63 al. 1 let. a LEtr écarté.
5.
La révocation de cette autorisation ne se justifie toutefois que si la pesée des intérêts à effectuer dans le cas d'espèce fait apparaître la mesure comme proportionnée (cf. art. 96 LEtr; <ref-ruling> consid. 2.2 p. 147 s.), étant toutefois précisé que la révocation d'une autorisation ensuite de la dissimulation d'une relation parallèle est une mesure qui sera en règle générale considérée comme étant proportionnée, sous réserve de circonstances particulières.
5.1. Dans le cadre de l'examen de la proportionnalité, il faut que la pesée des intérêts publics et privés effectuée dans le cas d'espèce fasse apparaître la mesure d'éloignement comme proportionnée aux circonstances. A cet égard, il faut prendre en considération, outre une éventuelle faute et sa gravité, la situation personnelle de l'étranger, son degré d'intégration, la durée de son séjour en Suisse ainsi que les inconvénients que lui et sa famille devraient subir si la mesure litigieuse était appliquée (<ref-ruling> consid. 4.3 p. 381).
5.2. En l'occurrence, l'autorité précédente a retenu que le recourant vivait certes depuis quinze ans en Suisse et s'exprimait couramment en français, mais qu'il avait vécu jusqu'à l'âge de 32 ans en Macédoine et qu'il retournait fréquemment dans ce pays. Elle a relativisé la durée du séjour dans la mesure où elle résultait de la dissimulation de la paternité et de la liaison du recourant à l'étranger. Retenant encore que ce dernier n'avait pas eu d'enfants avec sa première épouse et qu'il n'avait fait valoir aucun lien particulièrement intense avec des proches vivant en Suisse, elle a estimé que la mesure de révocation de l'autorisation d'établissement était proportionnée, le recourant pouvant ainsi retourner vivre auprès de sa femme et ses enfants.
5.3. Compte tenu de la situation atypique du recourant, et en particulier de ses longues années vécues en Suisse ainsi que de la durée de son mariage avec une ressortissante helvétique, l'appréciation de la proportionnalité de la mesure effectuée par l'autorité précédente ne saurait être confirmée. Contrairement à ce qu'a retenu le Tribunal cantonal, le recourant n'a pas vécu jusqu'à l'âge de 32 ans en Macédoine, puisque durant sept ans, celui-ci a travaillé en Suisse en tant que saisonnier. En outre, dans le cadre de l'examen de la proportionnalité, il n'est pas forcément nécessaire que l'étranger fasse montre de liens particulièrement intenses en Suisse. On relèvera encore que lors du dépôt de sa demande d'autorisation d'établissement en 2007, le recourant présentait un casier judiciaire vierge et ne faisait l'objet d'aucune poursuite (<ref-law>). Rien n'indique qu'il en serait autrement à ce jour. Dans ces conditions particulières, il convient de reconnaître le caractère disproportionné de la mesure tendant au renvoi du recourant dans son pays d'origine et d'admettre le recours en matière de droit public.
L'arrêt entrepris sera ainsi annulé et la cause renvoyée au Service cantonal, afin qu'il renonce à révoquer l'autorisation d'établissement du recourant et statue sur la demande de regroupement familial que ce dernier a déposée pour sa femme et ses enfants.
6.
Sur le vu de ce qui précède, il n'est pas perçu de frais de procédure (art. 66 al. 1 et 4 LTF). Le canton du Valais doit en outre verser au recourant une indemnité à titre de dépens (cf. <ref-law>). La cause est renvoyée au Tribunal cantonal pour qu'il procède à une nouvelle répartition des frais et dépens de la procédure qui s'est déroulée devant lui (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours en matière de droit public est admis et l'arrêt attaqué est annulé.
2.
La cause est renvoyée au Service cantonal pour qu'il procède dans le sens des considérants.
3.
La cause est renvoyée au Tribunal cantonal, afin qu'il statue à nouveau sur le sort des frais et dépens de la procédure devant lui.
4.
Le recours constitutionnel subsidiaire est irrecevable.
5.
Il n'est pas perçu de frais judiciaires.
6.
Une indemnité de partie, arrêtée à 2'000 fr., est allouée au recourant, à charge du canton du Valais.
7.
Le présent arrêt est communiqué au mandataire du recourant, au Service de la population et des migrations, au Conseil d'Etat et au Tribunal cantonal du canton du Valais, Cour de droit public, ainsi qu'au Secrétariat d'Etat aux migrations.
Lausanne, le 24 mai 2016
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Seiler
Le Greffier : Tissot-Daguette