Faits: A. X._, ressortissant bosniaque, né en 1982, est arrivé en Suisse le 4 janvier 2005. A la suite de son mariage, en février 2004, avec Y._, ressortissante serbe, titulaire d'une autorisation d'établissement dans le canton de Berne, il a obtenu une autorisation de séjour puis, le 13 janvier 2010, une autorisation d'établissement dans le canton de Neuchâtel, où les époux avaient annoncé leur arrivée le 1 er octobre 2007. X._ a déposé une requête en divorce le 16 février 2010. Il a expliqué qu'il avait découvert que sa femme était enceinte d'un autre homme. Le divorce des époux a été prononcé le 11 mars 2010 par le Tribunal civil du district de Neuchâtel. Le 29 novembre 2010, X._ a épousé dans son pays d'origine une compatriote, Z._ qui, le 7 décembre 2010, a déposé une demande de visa de long séjour à l'ambassade de Suisse de Sarajevo pour venir rejoindre son mari. Cette demande concernait également son fils A._, né le 20 février 2008, dont le père est X._. Ce dernier a expliqué au Service des migrations du canton de Neuchâtel (ci-après: le Service des migrations) qu'il avait eu une relation occasionnelle avec sa seconde épouse en mai 2007, qu'il était retourné en Bosnie-Herzégovine pour reconnaître l'enfant, mais n'avait plus eu de contact avec cette dernière jusqu'aux vacances d'été 2010, où ils avaient décidé de se marier. Le 7 juin 2011, il a également signalé que son épouse avait accouché d'un second enfant. B. Par décision du 28 juin 2011, le Service des migrations a révoqué l'autorisation d'établissement de X._ et lui a imparti un délai au 31 août 2011 pour quitter la Suisse. Il a également classé les demandes de regroupement familial déposées en faveur de Z._ et A._. Dans un recours du 16 août 2011, X._ a fait état de l'altération de son état de santé à la suite de la décision du 28 juin 2011 et a demandé la révocation des mesures d'expulsion jusqu'à nouvel avis du médecin. Par décision du 9 mars 2012, le Département de l'économie du canton de Neuchâtel (ci-après: le Département) a constaté que X._ ne contestait pas les motifs ayant présidé à la révocation de l'autorisation d'établissement. Il a estimé que seule la question de l'existence d'un cas individuel d'extrême gravité devait être examinée et que les conditions pour reconnaître la réalisation d'un tel cas sous l'angle médical n'étaient pas remplies. Au sujet des autres critères, il a notamment retenu que l'intéressé n'avait pas " respecté l'ordre juridique suisse en se prévalant d'une situation maritale qui n'existait plus que formellement pour obtenir son autorisation d'établissement, dissimulant par la même occasion la constitution d'une famille parallèle en Bosnie. " X._ a recouru contre cette décision auprès du Tribunal cantonal du canton de Neuchâtel, Cour de droit public, qui, par arrêt du 23 mai 2013, a rejeté le recours. La juridiction cantonale a considéré en bref que, dans la mesure où le recourant avait invoqué uniquement son état de santé et son statut de travailleur dans son " mémoire de recours du 16 août 2011 ", le Département n'avait pas à examiner les motifs sur lesquels s'était fondé le Service de la population pour révoquer l'autorisation d'établissement. Il en a déduit que seul l'examen d'un cas individuel d'extrême gravité pouvait faire l'objet du recours, mais qu'aucune autorisation de séjour ne pouvait être accordée au recourant à ce titre. C. Agissant par la voie du recours en matière de droit public, subsidiairement du recours constitutionnel subsidiaire, X._ conclut, sous suite de frais et dépens, à l'annulation de l'arrêt du Tribunal cantonal du 23 mai 2013. Il demande au Tribunal fédéral, à titre principal, de constater qu'il n'a pas commis un abus de droit en invoquant son mariage avec Mme Y._ et, par conséquent, de maintenir son autorisation d'établissement. A titre subsidiaire, il requiert le Tribunal fédéral de constater qu'il se trouve dans la situation d'un cas individuel d'extrême gravité et, partant, de lui accorder une autorisation de séjour. Le Tribunal cantonal se réfère à son arrêt et conclut au rejet du recours, de même que le Service des migrations qui estime " que les griefs soulevés par le recourant ont déjà été examinés par les différentes autorités de recours cantonales ". De son côté, le Département se réfère aux considérants de l'arrêt attaqué et conclut au rejet du recours dans la mesure où il est recevable. L'Office fédéral des migrations propose le rejet du recours.