Faits : A. A._, ressortissant kosovar né en 1976, a épousé une ressortissante portugaise au bénéfice d'une autorisation de séjour le 29 octobre 2005. Arrivé en Suisse le 4 février 2006, il s'est vu délivrer une autorisation de séjour par regroupement familial, régulièrement renouvelée jusqu'au 3 février 2011. Les époux se sont séparés en 2009 et leur divorce a été prononcé le 10 mars 2014. A._ est père de deux filles nées d'une précédente union et vivant au Kosovo, avec ses parents. Depuis son arrivée en Suisse, A._ n'a travaillé qu'épisodiquement. Il a été au chômage durant près de deux ans et a bénéficié de prestations de l'aide sociale au mois de février 2009 pour un montant de 500 francs. Au 3 décembre 2010, ses dettes s'élevaient à quelque 26'000 francs. B. Par décision du 10 janvier 2014, l'Office cantonal de la population et des migrations du canton de Genève s'est déclaré favorable à la prolongation de l'autorisation de séjour de l'intéressé, sous réserve de l'approbation du Secrétariat d'Etat aux migrations. Le 2 décembre 2014, celui-ci a refusé d'approuver la prolongation de l'autorisation de séjour en faveur de A._ et a prononcé son renvoi de Suisse. Ce dernier a contesté ce prononcé auprès du Tribunal administratif fédéral par acte du 20 janvier 2015. Par arrêt du 6 juin 2016, le Tribunal administratif fédéral a rejeté le recours. Il a jugé en substance que l'intéressé ne pouvait se prévaloir d'une intégration réussie pour demeurer en Suisse. C. A l'encontre de cet arrêt, A._ a déposé, le 13 juillet 2016, un recours en matière de droit public auprès du Tribunal fédéral. Il conclut, sous suite de frais et dépens, à son annulation ainsi que, principalement, à la prolongation de son autorisation de séjour et, subsidiairement, au renvoi de la cause au Tribunal administratif fédéral pour nouvelle décision au sens des considérants. Le Tribunal administratif fédéral a renoncé à se déterminer. Le Secrétariat d'Etat aux migrations a conclu au rejet du recours. Le recourant n'a pas formulé de nouvelles observations.