Faits: A. X._, ressortissant kosovar né en 1980, est arrivé en Suisse en janvier 1999. La demande d'asile qu'il y a déposée a été rejetée en juillet 1999; il a toutefois été autorisé à rester en Suisse jusqu'au 31 mai 2000 au bénéfice d'une admission à titre collectif. Après avoir quitté notre pays le 26 mai 2000 en bénéficiant de l'aide au retour, il y est revenu illégalement en juin 2001. Le 26 juillet 2002, il a été condamné à deux mois d'emprisonnement avec sursis pendant deux ans et à une amende de 300 fr. pour violation grave d'une règle de la circulation routière pour ne pas avoir observé les signaux, vol d'usage d'un véhicule, délit et contravention à la loi fédérale sur le séjour et l'établissement des étrangers et à la loi cantonale sur le contrôle des habitants. X._ s'est marié en 2004 avec une ressortissante suisse et a dès lors obtenu une autorisation de séjour annuelle, qui a été régulièrement prolongée jusqu'en 2009. Les conjoints se sont séparés en 2009. L'épouse a accouché d'un enfant en 1999, dont il a été établi par jugement en 2011 qu'il n'était pas le fils de X._. Le divorce des époux a été prononcé en 2012. B. Par décision du 24 janvier 2012, le Service des migrations du canton de Neuchâtel (ci-après: le Service des migrations) a refusé à X._ la prolongation de son autorisation de séjour en raison de son parcours professionnel, comprenant des périodes de chômage et d'accident, de la perception de l'aide sociale et de sa situation financière obérée. Il a par ailleurs considéré que l'intéressé ne se trouvait pas dans une situation d'extrême gravité ni ne présentait de raisons personnelles majeures justifiant la prolongation de son séjour en Suisse. Le 29 mai 2012, le Département de l'économie du canton de Neuchâtel (ci-après: le Département) a rejeté le recours déposé par X._ contre la décision du Service des migrations. Le Département a retenu que l'intéressé parlait le français, l'allemand et le suisse-allemand, et que malgré une longue période de chômage, il avait réalisé un gain intermédiaire attestant un souci d'indépendance financière. L'accident qu'il avait subi ne pouvait lui être reproché, pas plus que l'aide sociale, perçue durant deux mois seulement et pour un faible montant. En outre, plusieurs personnes témoignaient de la bonne intégration de X._, qui respectait l'ordre juridique suisse depuis sa condamnation pénale de 2002. En revanche, le Département a confirmé que son fort endettement parlait en défaveur d'une intégration réussie et que la poursuite du séjour en Suisse ne s'imposait ni en raison d'une situation personnelle d'extrême gravité, ni pour des raisons personnelles majeures. Le 2 juillet 2012, X._ a recouru devant la Cour de droit public du Tribunal cantonal de la République et canton de Neuchâtel (ci-après: le Tribunal cantonal) contre la décision du Département. Il a soutenu que l'existence des poursuites et actes de défaut de biens à son encontre ne constituait pas un élément permettant de nier son intégration et que leur montant avait diminué depuis le 6 février 2012. Il a relevé qu'à la suite de la conclusion d'un nouveau contrat de travail le 13 juin 2012, son salaire faisait l'objet d'une saisie mensuelle de 1'000 fr. et que l'entier de son 13 ème salaire était saisi, de sorte qu'il serait en mesure d'assainir sa situation financière sur une période de 6.4 ans. Par arrêt du 17 avril 2013, le Tribunal cantonal a rejeté le recours et transmis le dossier de la cause au Service des migrations pour fixation d'un nouveau délai de départ. C. Agissant par la voie du recours en matière de droit public, X._ demande au Tribunal fédéral, sous suite de frais et dépens, d'annuler la décision du Tribunal cantonal et de lui octroyer une prolongation de son autorisation de séjour, voire une autorisation de séjour conditionnelle, subsidiairement de renvoyer la cause à l'autorité inférieure ou au Service des migrations pour nouvelle décision dans le sens des considérants. Invités à se déterminer, le Tribunal cantonal, le Département, le Service des migrations et l'Office fédéral des migrations n'ont pas formulé d'observations et ont conclu au rejet du recours. Par ordonnance du 23 mai 2013, le Président de la IIe Cour de droit public du Tribunal fédéral a admis la requête d'effet suspensif contenue dans le recours. 