Faits : A. A._, ressortissant du Sénégal né le 15 février 1982, est entré légalement en Suisse le 11 avril 2008 en vue de son mariage avec une ressortissante suisse. A la suite de cette union célébrée le 6 juin 2008, A._ a été mis au bénéfice d'une autorisation de séjour. Les époux ont eu deux enfants, B._, né le 21 mars 2008, et C._, née le 15 mai 2010, qui sont de nationalité suisse. Le couple s'est séparé le 3 novembre 2012. Le Tribunal civil de l'arrondissement de l'Est vaudois a, le 7 février 2013, ratifié la convention de mesures protectrices de l'union conjugale établie par les époux. La garde des enfants a été attribuée à leur mère. A._ s'est vu accorder un libre droit de visite et a été astreint, dès qu'il aurait trouvé un emploi lui procurant un salaire mensuel net de 2'800 fr., au versement d'une contribution d'entretien de 800 fr. Il n'a jusqu'à présent pas versé de pensions alimentaires. Depuis le mois de décembre 2015, A._ est employé deux jours par semaine, son revenu mensuel net s'élevant à 1'265 fr. 50. Jusqu'alors, il n'avait travaillé qu'épisodiquement. Depuis son arrivée en Suisse, A._ a été inscrit au chômage durant près de quatre mois et a bénéficié du revenu d'insertion de manière quasi ininterrompue, le montant total perçu à cet titre s'élevant à 218'755 fr. au 12 octobre 2015. Il est actuellement encore tributaire de cette aide. A._ ne fait pas l'objet de poursuites. Sur le plan pénal, A._ a été condamné, par ordonnance pénale du Ministère public de la Confédération du 26 février 2015, à une peine pécuniaire de dix jours-amende pour falsification d'un timbre officiel. B. Par décision du 24 novembre 2014, le Service de la population du canton de Vaud a refusé de délivrer à A._ une autorisation d'établissement à titre anticipé. Il s'est en revanche déclaré disposé à renouveler son autorisation de séjour, sous réserve de l'approbation du Secrétariat d'Etat aux migrations (ci-après: SEM). Le 5 octobre 2015, 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. L'intéressé a contesté ce prononcé auprès du Tribunal administratif fédéral par acte du 6 novembre 2015. Par arrêt du 19 octobre 2016, le Tribunal administratif fédéral a rejeté le recours. Il a jugé en bref que A._ ne pouvait se prévaloir ni d'une intégration réussie, ni de raisons personnelles majeures. C. Agissant par la voie du recours en matière de droit public, A._ demande au Tribunal fédéral, sous suite de frais et dépens, outre l'effet suspensif, de réformer l'arrêt du Tribunal administratif fédéral du 19 octobre 2016 en ce sens que l'autorisation de séjour est prolongée; subsidiairement d'annuler l'arrêt entrepris et de renvoyer la cause au Tribunal administratif fédéral pour nouvelle décision dans le sens des considérants. Par ordonnance du 24 novembre 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 a renoncé à prendre position. Le SEM a conclu au rejet du recours. Le recourant n'a pas formulé de nouvelles observations.