Faits :
A.
X._, ressortissant kosovar né en 1974, est entré une première fois en Suisse le 14 mai 1999 afin d'y déposer une demande d'asile. Cette demande a été rejetée le 17 janvier 2000. Après avoir tenté en vain d'obtenir un titre de séjour et avoir séjourné illégalement en Suisse, l'intéressé a épousé une ressortissante helvétique le 18 août 2006. Par décision du 22 mai 2007, le Service de la population du canton de Vaud a mis X._ au bénéfice d'une autorisation de séjour au titre du regroupement familial. Les époux se sont séparés au plus tard en février 2011, au retour d'un voyage d'une année à l'étranger de la femme de l'intéressé. Le 11 janvier 2012, celui-ci a déposé une demande d'autorisation d'établissement.
X._ a fait l'objet de plusieurs condamnations pénales, notamment pour des infractions à la LEtr (RS 142.20), respectivement à l'ancienne loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (aLSEE; RO 49 279), et à la LCR (RS 741.01). Au 6 janvier 2012, il présentait des dettes pour un montant de 27'612 fr. 25. Il n'a jamais été au chômage, ni émargé à l'aide sociale.
B.
Par décision du 3 janvier 2014, le Service de la population du canton de Vaud a refusé de mettre X._ au bénéfice d'une autorisation d'établissement, mais s'est déclaré favorable à la prolongation de son autorisation de séjour, malgré la séparation des époux X._.
Par décision du 3 juillet 2014, le Secrétariat d'Etat aux migrations (ci-après: le Secrétariat d'Etat) a refusé d'approuver la prolongation de l'autorisation de séjour de l'intéressé. Celui-ci a contesté ce prononcé auprès du Tribunal administratif fédéral par acte du 8 septembre 2014.
Par arrêt du 21 mars 2016, le Tribunal administratif fédéral a rejeté le recours de X._. Il a jugé en bref que celui-ci ne pouvait se prévaloir ni d'une intégration réussie en Suisse, ni de raisons personnelles majeures pour pouvoir prétendre à la prolongation de son autorisation de séjour.
C.
Agissant par la voie du recours en matière de droit public, X._ demande en substance au Tribunal fédéral, sous suite de frais et dépens, outre l'effet suspensif, d'annuler l'arrêt du 21 mars 2016 du Tribunal administratif fédéral et d'ordonner au Secrétariat d'Etat d'approuver la prolongation de son autorisation de séjour; subsidiairement d'annuler l'arrêt précité et de renvoyer la cause au Tribunal administratif fédéral pour nouvelle décision dans le sens des considérants. Il se plaint de violation du droit fédéral.
Par ordonnance du 4 mai 2016, le Président de la IIe Cour de droit public du Tribunal fédéral a admis la demande d'effet suspensif.
Le Tribunal administratif fédéral renonce à se déterminer sur le recours. Le Secrétariat d'Etat conclut à son rejet.

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 à l'encontre des 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 suffit toutefois qu'il existe un droit potentiel à l'autorisation, étayé par une motivation soutenable, pour que cette clause d'exclusion ne s'applique pas et que, partant, la voie du recours en matière de droit public soit ouverte. La question de savoir si les conditions d'un tel droit sont effectivement réunies relève du fond (<ref-ruling> consid. 1.1 p. 179 s.). En l'occurrence, du moment que le recourant vit séparé d'une ressortissante suisse, l'art. 50 LEtr est potentiellement de nature à lui conférer un droit à une autorisation de séjour, de sorte que la voie du recours en matière de droit public est ouverte.
1.2. Pour le surplus, l'arrêt attaqué est une décision finale (<ref-law>), rendue par le Tribunal administratif fédéral (<ref-law>) dans une cause de droit public (<ref-law>). Le recours ayant de surcroît été déposé en temps utile (<ref-law>) et dans les formes requises (<ref-law>), par le recourant qui est atteint par la décision entreprise et a un intérêt digne de protection à son annulation ou à sa modification, de sorte qu'il faut lui reconnaître la qualité pour recourir (<ref-law>), il est partant recevable.
2.
Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (cf. <ref-law>). Le recours ne peut critiquer les constatations de fait que si les faits ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law>, et si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-law>), ce que la partie recourante doit démontrer d'une manière circonstanciée, conformément aux exigences de motivation de l'<ref-law> (cf. <ref-ruling> consid. 1.4.3 p. 254 s.). La notion de "manifestement inexacte" correspond à celle d'arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 2.1 p. 450).
3.
Le litige porte sur le point de savoir si le recourant peut se prévaloir d'une intégration suffisante en Suisse, malgré des condamnations pénales et des poursuites, pour pouvoir prétendre, après une durée de plus de trois ans de mariage avec une ressortissante suisse, à la prolongation de son autorisation de séjour.
4.
Se plaignant d'une violation de l'art. 50 al. 1 let. a LEtr, le recourant reproche au Tribunal administratif fédéral d'avoir nié à tort la réussite de son intégration en Suisse. L'arrêt attaqué ne tiendrait, d'après lui, pas compte de la nature et de la gravité des infractions pénales. Il n'examinerait pas non plus à suffisance sa réelle situation financière et son intégration sociale.
4.1. Le principe de l'intégration doit permettre aux étrangers dont le séjour est légal et durable de participer à la vie économique, sociale et culturelle de la Suisse (art. 4 al. 2 LEtr). D'après l'art. 77 al. 4 de l'ordonnance du 24 octobre 2007 relative à l'admission, au séjour et à l'exercice d'une activité lucrative (OASA; RS 142.201), un étranger s'est bien intégré, au sens de l'art. 50 al. 1 let. a LEtr, notamment lorsqu'il respecte l'ordre juridique suisse et les valeurs de la Constitution fédérale (let. a) et qu'il manifeste sa volonté de participer à la vie économique et d'apprendre la langue nationale parlée au lieu de domicile (let. b). Selon l'art. 4 de l'ordonnance du 24 octobre 2007 sur l'intégration des étrangers (OIE; RS 142.205), la contribution des étrangers à l'intégration se manifeste notamment par le respect de l'ordre juridique et des valeurs de la Constitution fédérale (let. a), par l'apprentissage de la langue nationale parlée sur le lieu de domicile (let. b), par la connaissance du mode de vie suisse (let. c) et par la volonté de participer à la vie économique et d'acquérir une formation (let. d). L'adverbe "notamment", qui est employé tant à l'art. 77 al. 4 OASA qu'à l'<ref-law>, illustre le caractère non exhaustif des critères d'intégration qui sont énumérés par ces dispositions et met aussi en exergue le fait que la notion "d'intégration réussie" doit s'examiner à l'aune d'une appréciation globale des circonstances. Dans l'examen de ces critères d'intégration, les autorités compétentes disposent d'un large pouvoir d'appréciation que le Tribunal fédéral ne revoit qu'avec retenue (cf. art. 54 al. 2 et 96 al. 1 LEtr et <ref-law>; arrêts 2C_352/2014 du 18 mars 2015 consid. 4.2 et les références citées).
Selon la jurisprudence, il n'y a pas d'intégration réussie lorsque l'étranger n'exerce pas d'activité lucrative qui lui permette de couvrir ses besoins et qu'il dépend des prestations sociales pendant une période relativement longue (arrêts 2C_748/2014 du 12 janvier 2015 consid. 3.2; 2C_352/2014 du 18 mars 2015 consid. 4.3; 2C_385/2014 du 19 janvier 2015 consid. 4.1). A l'inverse, le fait pour une personne de ne pas avoir commis d'infractions pénales et de pourvoir à son revenu sans recourir à l'aide sociale ne permet pas à lui seul de retenir une intégration réussie (arrêts 2C_352/2014 du 18 mars 2015 consid. 4.3; 2C_14/2014 du 27 août 2014 consid. 4.6.1, non publié in <ref-ruling>). Des périodes d'inactivité de durée raisonnable n'impliquent pas forcément une absence d'intégration professionnelle. Il n'est pas indispensable que l'étranger fasse montre d'une carrière professionnelle requérant des qualifications spécifiques; l'intégration réussie au sens de l'art. 50 al. 1 let. a LEtr n'implique en effet pas nécessairement la réalisation d'une trajectoire professionnelle particulièrement brillante au travers d'une activité exercée sans discontinuité. L'essentiel en la matière est que l'étranger subvienne à ses besoins, n'émarge pas à l'aide sociale et ne s'endette pas de manière disproportionnée (arrêts 2C_352/2014 du 18 mars 2015 consid. 4.3; 2C_385/2014 du 19 janvier 2015 consid. 4.1). L'intégration réussie d'un étranger qui est actif professionnellement en Suisse, dispose d'un emploi fixe, a toujours été financièrement indépendant, se comporte correctement et maîtrise la langue locale ne peut être niée qu'en la présence de circonstances particulièrement sérieuses (arrêts 2C_352/2014 du 18 mars 2015 consid. 4.3; 2C_930/2012 du 10 janvier 2013 consid. 3.1). L'absence de liens sociaux très étroits en Suisse n'exclut pas non plus d'emblée l'existence d'une intégration réussie, de même que l'absence de vie associative (arrêts 2C_352/2014 du 18 mars 2015 consid. 4.3; 2C_930/2012 du 10 janvier 2013 consid. 3.1).
4.2. Contrairement à ce que lui reproche le recourant, le Tribunal administratif fédéral a dûment tenu compte des différents critères pertinents pour évaluer son degré d'intégration en Suisse, avant de parvenir à la conclusion que l'intégration de l'intéressé était insuffisante pour lui permettre de demeurer en Suisse au bénéfice de l'art. 50 al. 1 let. a LEtr.
Sous l'angle de l'intégration socio-économique, d'abord, les précédents juges ont en particulier relevé que le recourant a certes régulièrement exercé diverses activités lucratives depuis son arrivée en Suisse en 2002. Ils ont toutefois relevé que le premier contrat de travail de l'intéressé, datant de 2004, a été conclu auprès de l'entreprise individuelle du frère de celui-ci. Son deuxième contrat, daté de 2006, auprès d'une société à responsabilité limitée détenue par son frère et sa belle-soeur, alors qu'il était en Suisse sans autorisation. Le recourant a ensuite fondé sa propre société à responsabilité limitée avec son épouse en avril 2008, la faillite de cette société ayant été prononcée en 2010. Par la suite, le recourant a bénéficié de deux contrats de travail auprès de sociétés dont il était patron, respectivement dont il semble avoir été gérant. Ces sociétés ont également fait faillite dans les deux ans suivant leur fondation. Depuis le 1 er juin 2014, le recourant travaille pour une nouvelle entreprise. Il a perçu un salaire mensuel net moyen, entre les mois de juillet 2014 et août 2015, de 2'516 fr. En outre, selon un extrait du registre des poursuites daté du 16 octobre 2015, le recourant présente des poursuites pour un montant de 25'451 fr. 35, principalement en raison d'impôts impayés. Il n'a toutefois jamais émargé à l'assistance sociale ni perçu des indemnités de l'assurance-chômage. Le Tribunal administratif fédéral a ainsi considéré que le recourant cherche à s'occuper professionnellement, mais les dettes qu'il présente ne sont pas négligeables, raison pour laquelle il ne remplit que partiellement la volonté de participer à la vie économique.
Quant à son intégration sociale, respectivement son apprentissage de la langue nationale parlée au lieu de domicile, l'autorité précédente a retenu que le recourant avait appris à suffisance le français durant ses treize années de séjour (légales ou non) en Suisse. Le recourant ne fait cependant pas partie d'associations et n'a pas de vie associative. Il n'a jamais allégué s'être créé un cercle de connaissances ou un réseau social, les seules connaissances figurant au dossier étant ses frères et sa belle-soeur. Le Tribunal administratif fédéral a donc considéré que cela ne suffisait pas pour retenir que l'intégration sociale était réussie.
Surtout, le recourant a été condamné à plusieurs reprises depuis son arrivée en Suisse. L'autorité précédente a ainsi constaté que le recourant est revenu sur le territoire suisse illégalement en 2002 après s'être vu refuser l'asile en 2000. Il a vécu et travaillé en Suisse sans autorisation jusqu'en mai ou juin 2005, puis depuis novembre 2005 jusqu'à l'obtention de son autorisation de séjour le 22 mai 2007. Durant cette période, il a été condamné les 25 mai 2005 et 22 juin 2006 pour des délits contre la aLSEE. Le 5 mars 2010, il a été condamné pour un excès de vitesse, le 8 mai 2013 pour infraction à la législation routière, séjour illégal et exercice d'une activité lucrative sans autorisation, ainsi que pour avoir employé des étrangers sans autorisation. Enfin, le 20 février 2014, le recourant a été condamné pour infraction grave à la législation routière. L'ensemble de ses peines représente ainsi un total de 176 jours-amende et 3'220 fr. d'amende. Le Tribunal administratif fédéral en a déduit que le recourant n'a guère démontré de respect envers les décisions des autorités suisses de police des étrangers et que son comportement n'est pas en adéquation avec le respect de l'ordre juridique suisse.
4.3. Sur la base de tous ces éléments, l'examen global de l'autorité précédente niant l'intégration réussie de l'intéressé ne procède pas d'une appréciation arbitraire des faits ni ne viole le droit fédéral des étrangers. Même si certains éléments sont certes favorables au recourant (notamment la maîtrise d'une langue nationale ou la volonté de tendre à une intégration professionnelle), ceux-ci ne suffisent pas. On doit en effet relever que les infractions pénales perpétrées au cours du séjour en Suisse sont loin d'être anodines (en particulier l'engagement de personnel étranger illégal et la violation grave des dispositions de la LCR) et ne respectent pas l'ordre juridique helvétique (cf. <ref-law>). De plus, le recourant présente une situation économique précaire, ou à tout le moins floue sur une longue période de temps (le recourant mentionnant d'ailleurs lui-même dans son recours être soutenu financièrement par ses proches), et un montant de poursuites relativement important. Contrairement à ce qu'il fait valoir, le Tribunal administratif fédéral a considéré le nombre d'infractions, leur gravité et la durée de séjour en Suisse dans son appréciation. Celui-ci n'a au demeurant pas uniquement pris en compte les infractions commises pour nier l'intégration du recourant, mais a considéré la situation dans son ensemble.
4.4. Sur le vu de ce qui précède, le recourant ne remplit pas les conditions de l'art. 50 al. 1 let. a LEtr. Même s'il ne le conteste pas, on peut encore relever que l'appréciation du Tribunal administratif fédéral en relation avec l'art. 50 al. 1 let. b et al. 2 LEtr ne porte pas flanc à la critique, pas plus que le résultat de l'examen de la proportionnalité de la mesure. L'autorité précédente a en particulier retenu à raison que le recourant avait passé toute sa jeunesse dans son pays d'origine, où se trouvent encore des membres de sa famille dont ses deux filles nées d'une précédente union. Le recourant a ainsi gardé des liens étroits avec le Kosovo, pays dans lequel il s'est rendu à de nombreuses reprises ces dernières années. Par conséquent, on ne peut reprocher à l'autorité précédente d'avoir confirmé le refus de prolonger l'autorisation de séjour du recourant sur cette base. Cela conduit au rejet de son recours devant le Tribunal fédéral.
5.
Succombant, le recourant doit supporter les frais judiciaires (<ref-law>). Il n'est pas alloué de dépens (art. 68 al. 1 et 3 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué à la mandataire du recourant, au Secrétariat d'Etat aux migrations, au Tribunal administratif fédéral, Cour III et au Service de la population du canton de Vaud.
Lausanne, le 4 octobre 2016
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Seiler
Le Greffier : Tissot-Daguette