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.