Faits : A. X._, ressortissant algérien né en 1983, est arrivé en Suisse le 9 octobre 2002. Il y a déposé une demande d'asile sous une fausse identité. Par décision du 17 octobre 2003, l'ancien Office fédéral des réfugiés (actuellement le Secrétariat d'Etat aux migrations; ci-après: le Secrétariat d'Etat) n'est pas entré en matière sur la demande d'asile de l'intéressé. Le renvoi de ce dernier n'a pas pu être exécuté en raison de sa disparition. Le 30 décembre 2010, l'intéressé s'est marié avec une ressortissante suisse, avec laquelle il avait déjà un enfant, né en février 2009. En mai 2010, le couple a eu un deuxième enfant. Suite à son mariage, il a obtenu une autorisation de séjour. Les époux se sont séparés le 1 er mars 2013. Par ordonnance de mesures protectrices de l'union conjugale, l'intéressé a obtenu un droit de visite sur ses enfants, limité à deux fois par mois, dans un Point Rencontre. Entre 2003 et 2013, X._ a été condamné à neuf reprises, à des peines variant entre cinq jours et six mois de peine privative de liberté, pour des infractions diverses, notamment des infractions contre le patrimoine et l'intégrité corporelle ainsi que des contraventions à la LStup (RS 812.121). Au 28 août 2013, l'intéressé faisait l'objet de poursuites pour un montant de 14'156 fr. 50. Le 22 avril 2014, le Service de la population du canton de Vaud (ci-après: le Service de la population) a informé X._ qu'il était favorable à la prolongation de son autorisation de séjour. B. Par décision du 11 décembre 2014, l'ancien Office fédéral des migrations (actuellement le Secrétariat d'Etat) a refusé de donner son approbation à la prolongation de l'autorisation de séjour de l'intéressé et a prononcé son renvoi de Suisse. X._ a recouru contre cette décision auprès du Tribunal administratif fédéral le 28 janvier 2015. Par arrêt du 26 novembre 2015, le Tribunal administratif fédéral a rejeté le recours de X._, jugeant en substance que celui-ci ne pouvait se prévaloir d'une durée suffisante d'union conjugale ou de raisons personnelles majeures pour prétendre à demeurer en Suisse. 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, outre l'effet suspensif, d'annuler l'arrêt du Tribunal administratif fédéral du 26 novembre 2015 et d'inviter le Secrétariat d'Etat à approuver la prolongation de son autorisation de séjour; subsidiairement, d'annuler l'arrêt précité et de renvoyer la cause au Secrétariat d'Etat pour nouvelle décision dans le sens des considérants. Il se plaint d'établissement inexact des faits et de violation du droit d'être entendu, ainsi que de violation du droit fédéral et du droit international. Par ordonnance du 20 janvier 2016, le Juge présidant 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. Le Secrétariat d'Etat conclut au rejet du recours.