Faits: A. X._, ressortissant kosovar, né en 1967, a travaillé en Suisse comme saisonnier de 1990 à 1998, puis a déposé une demande d'asile rejetée par l'Office fédéral des réfugiés le 12 octobre 1999. Dans son pays d'origine, X._ a eu trois enfants, nés en 1994, 1997 et 2000, avec son ex-épouse, dont il a divorcé le 11 mars 2004. Le 26 octobre 2006, X._ s'est marié dans le canton de Neuchâtel avec une ressortissante suisse, Y._, née en 1964, et a obtenu une autorisation de séjour, régulièrement renouvelée jusqu'au 26 octobre 2009. Avisé que le couple vivait séparé depuis mi-septembre 2008 et que le divorce des époux avait été prononcé le 7 septembre 2010, le Service des migrations du canton de Neuchâtel (ci-après: le Service des migrations) a refusé de prolonger l'autorisation de séjour de X._, par décision du 13 décembre 2011. Saisi d'un recours de l'intéressé contre cette décision, le Département de l'économie du canton de Neuchâtel (ci-après: le Département) l'a rejeté, par prononcé du 3 octobre 2012. Il a retenu en bref que l'union conjugale ayant duré moins de trois ans, le recourant ne pouvait bénéficier d'une autorisation de séjour sur la base de l'art. 50 al. 1 let. a de la loi fédérale sur les étrangers (LEtr; RS 142.20) et qu'il ne remplissait pas davantage les conditions du cas de rigueur au sens de l'art. 50 al. 1 let. b et al. 2 LEtr. Divorcé de son épouse suisse avec laquelle il n'avait pas eu d'enfant, il ne pouvait pas non plus se prévaloir de l'art. 8 § 1 CEDH. B. X._ a recouru contre ce prononcé auprès de la Cour de droit public du Tribunal cantonal du canton de Neuchâtel (ci-après: le Tribunal cantonal), en faisant valoir que les conditions de l'art. 50 al. 1 let. a et b et al. 2 étaient réunies et qu'il pouvait se prévaloir de l'art. 8 § 1 CEDH en raison de la relation qu'il entretenait depuis quatre ans avec son amie suisse. Par arrêt du 22 mai 2013, le Tribunal cantonal a rejeté le recours. Il a retenu que seul le refus de la prolongation de l'autorisation de séjour en application de l'art. 50 al. 1 let. b et al. 2 LEtr pouvait faire l'objet du recours, dès lors que, devant le Département, le recourant s'était uniquement attaché à démontrer que des raisons personnelles majeures justifiaient la poursuite de son séjour en Suisse, mais que les conditions pour obtenir une autorisation de séjour à ce titre n'étaient pas remplies. Comme le recourant n'avait pas invoqué l'art. 50 al. 1 let. a LEtr ni l'art. 8 CEDH devant le Département, il n'avait pas à examiner ces aspects qui sortaient de l'objet du litige. 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 22 mai 2013 et demande au Tribunal fédéral de prolonger son 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, sous suite de frais. Le Département a répondu tardivement qu'il n'avait pas d'observations à formuler. L'Office fédéral des migrations propose le rejet du recours. D. Par ordonnance présidentielle du 27 juin 2013, la demande d'effet suspensif présentée par le recourant a été admise. 