Faits :
A.
X._, ressortissant de la République démocratique du Congo né en 1967, a déposé une demande d'asile en Suisse en 1998. Après que cette demande a été rejetée sur recours par la Commission suisse de recours en matière d'asile (actuellement le Tribunal administratif fédéral) et qu'une demande de révision subséquente a été déclarée irrecevable, l'intéressé a disparu en mai 1999. Il a déposé une deuxième demande d'asile le 28 mai 2002, qui a également été rejetée, sur recours, par la Commission suisse de recours en matière d'asile, le 12 août 2003.
Le 21 avril 2004, X._ est devenu père d'un garçon issu de sa relation avec une ressortissante italienne née en 1977 et titulaire d'une autorisation d'établissement UE/AELE. Il a épousé cette dernière le 11 mars 2005 et a été mis au bénéfice d'une autorisation de séjour au titre du regroupement familial. Les époux se sont séparés au mois d'août 2006. Le divorce a été prononcé le 25 février 2011. X._ a obtenu un droit de visite sur son fils. La mère de ce dernier s'est vue attribuer l'autorité parentale et la garde. Le 24 mars 2010, elle a déposé une requête auprès d'un tribunal civil, afin que l'employeur du père de son fils verse mensuellement et d'avance sur son compte la contribution d'entretien pour celui-ci.
Par jugement du 26 juillet 2011, l'intéressé a été condamné à 400 heures de travail d'intérêt général, avec sursis pendant deux ans, ainsi qu'à une amende de 700 fr. pour escroquerie.
Le 11 avril 2012, l'intéressé a reconnu sa fille, ressortissante congolaise née en 2011, issue d'une relation avec une compatriote, née en 1994, requérante d'asile déboutée.
Par décision du 18 avril 2013, le Service des migrations de la République et canton de Neuchâtel (ci-après: le Service des migrations) s'est déclaré favorable à la prolongation de l'autorisation de séjour de l'intéressé, sous réserve de l'approbation de l'Office fédéral des migrations (actuellement le Secrétariat d'Etat aux migrations; ci-après: le Secrétariat d'Etat).
B.
Par décision du 27 novembre 2013, le Secrétariat d'Etat a refusé d'approuver la prolongation de l'autorisation de séjour de X._ et a prononcé son renvoi de Suisse. Par acte du 20 janvier 2014, celui-ci a recouru contre ce prononcé auprès du Tribunal administratif fédéral.
Par arrêt du 1 er décembre 2015, le Tribunal administratif fédéral a rejeté le recours de X._. Après avoir considéré que ce dernier ne pouvait pas se prévaloir d'une autorisation de séjour en application de l'ALCP (RS 0.142.112.681), il a jugé en bref que la poursuite du séjour en Suisse ne s'imposait pas non plus pour des raisons personnelles majeures.
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 1 er décembre 2015 et, partant, la décision du Secrétariat d'Etat du 27 novembre 2013, ainsi que de lui octroyer une autorisation de séjour. Il se plaint d'une violation du droit fédéral et international.
Par ordonnance du 23 février 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 à prendre position et le Secrétariat d'Etat se réfère à l'arrêt contesté.

Considérant en droit :
1.
1.1. Le recourant se prévaut en particulier des art. 50 al. 1 let. b LEtr (RS 142.20) ainsi que 8 CEDH. Dans les deux cas, il invoque de manière soutenable son droit à entretenir une relation avec son fils de nationalité italienne au bénéfice d'une autorisation d'établissement UE/AELE. Son recours échappe par conséquent au motif d'irrecevabilité prévu à l'art. 83 let. c ch. 2 LTF (<ref-ruling> consid. 3.3 p. 500 ss). Au surplus, déposé en temps utile (<ref-law>) et dans les formes prescrites par la loi (<ref-law>), par le destinataire de l'arrêt attaqué qui a un intérêt digne de protection à son annulation ou à sa modification (<ref-law>), le présent recours, dirigé contre un arrêt final (<ref-law>) du Tribunal administratif fédéral (<ref-law>) rendu dans une cause de droit public (<ref-law>), est recevable, sous réserve de ce qui suit.
1.2. La conclusion tendant à l'annulation de la décision du Secrétariat d'Etat est irrecevable en raison de l'effet dévolutif complet du recours auprès du Tribunal administratif fédéral (<ref-ruling> consid. 1.2 p. 543).
2.
Citant les art. 29 Cst. et 6 CEDH, le recourant invoque en premier lieu une violation de son droit d'être entendu. Il estime que le Tribunal administratif fédéral n'a pas attendu qu'il transmette un extrait de son casier judiciaire pour statuer et ne s'est pas prononcé en prenant en compte un état des faits actualisé.
2.1. 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).
Le droit d'être entendu garanti par l'art. 29 al. 2 Cst. comprend notamment le droit pour l'intéressé de s'exprimer sur les éléments pertinents avant qu'une décision ne soit prise touchant sa situation juridique, de produire des preuves pertinentes, d'obtenir qu'il soit donné suite à ses offres de preuves pertinentes, de participer à l'administration des preuves essentielles ou à tout le moins de s'exprimer sur son résultat, lorsque cela est de nature à influer sur la décision à rendre (<ref-ruling> consid. 2.3 p. 282). L'autorité peut cependant renoncer à procéder à des mesures d'instruction lorsque les preuves administrées lui ont permis de former sa conviction et que, procédant d'une manière non arbitraire à une appréciation anticipée des preuves qui lui sont encore proposées, elle a la certitude que ces dernières ne pourraient l'amener à modifier son opinion (<ref-ruling> consid. 2.2 p. 210; <ref-ruling> consid. 2.1 p. 428 s.).
2.2. Dans un premier temps, le recourant estime que l'autorité précédente aurait dû attendre la production de l'extrait de son casier judiciaire avant de statuer. Il n'explique toutefois pas en quoi cet extrait aurait eu une quelconque incidence sur l'issue de la cause. De plus, on ajoutera que dans son courrier du 1 er septembre 2015 adressé à l'autorité précédente et faisant suite à une ordonnance de cette dernière relative à la production de divers moyens de preuve, le recourant a indiqué que, selon toute vraisemblance, il " devrait parvenir à (...) recevoir (l'extrait de son casier judiciaire) dans le courant de la semaine prochaine ". Au vu de cette affirmation et sans autres indications subséquentes du recourant, on ne saurait reprocher au Tribunal administratif fédéral d'avoir statué en l'absence de ce moyen de preuve trois mois plus tard.
Le recourant reproche également à l'autorité précédente d'avoir statué sans tenir compte de ses indications quant à la fréquence de l'exercice de son droit de visite sur son fils, fournies dans son courrier du 1 er septembre 2015. On doit toutefois relever que le Tribunal administratif fédéral, dans son ordonnance du 15 juillet 2015, avait demandé au recourant de démontrer, pièces justificatives à l'appui, les relations qu'il entretenait avec ses enfants, ce qu'il n'a pas fait. L'autorité précédente a pris en compte cette absence de moyen de preuve dans l'arrêt entrepris. Certes, le recourant a fourni trois attestations de versements. Toutefois, contrairement à ce qu'il affirme, celles-ci ont également été prises en compte dans l'arrêt contesté. De plus, et pour autant que ces moyens de preuve aient une incidence sur l'issue de la cause, ce que le recourant ne démontre pas à suffisance, ils ne sont de toute façon que peu probants, puisqu'ils ne permettent pas de déterminer quels sont les expéditeurs et destinataires des versements.
Dans ces conditions, en tant que le recourant invoque une violation de son droit d'être entendu, son grief doit être écarté. Le Tribunal fédéral vérifiera donc la correcte application du droit sur la seule base des faits retenus par l'autorité précédente.
3.
Le recourant invoque la violation des art. 50 al. 1 let. b LEtr et 8 CEDH, en ce que le Tribunal administratif fédéral n'a pas apprécié à leur juste valeur les liens qu'il entretient avec ses deux enfants.
3.1. En premier lieu, il convient d'emblée de mentionner que le recourant ne saurait être suivi lorsqu'il invoque ses liens avec sa fille, ressortissante congolaise née en 2011, pour fonder un droit à une autorisation de séjour. Selon les faits retenus par le Tribunal administratif fédéral, cette enfant ne bénéficie en effet d'aucun droit de présence assuré en Suisse qui permettrait au recourant de prétendre à une autorisation de séjour au titre du regroupement familial inversé (cf. <ref-ruling> consid. 3.3 p. 148; <ref-ruling> consid. 3.1 p. 354 s.). Que le recourant s'acquitte de manière régulière de la contribution d'entretien et qu'il partage du temps avec elle n'y change rien.
3.2. A l'instar de ce qu'a retenu le Tribunal administratif fédéral, il faut constater que le recourant ne saurait pas plus invoquer l'ALCP pour prétendre à l'octroi d'une autorisation de séjour en Suisse, ce que celui-ci ne fait d'ailleurs pas. Certes, son fils est de nationalité italienne et bénéficie d'une autorisation d'établissement UE/AELE en Suisse. Toutefois, comme l'a retenu l'autorité précédente, le recourant n'a ni l'autorité parentale, ni la garde sur son enfant. Or, la garde d'un enfant au bénéfice d'un droit de séjour en Suisse est une condition essentielle, selon la jurisprudence de la Cour de justice de l'Union européenne (arrêt du 19 octobre 2004 C-200/02 Zhu et Chen, n° 45 ss), reprise par le Tribunal fédéral (arrêt 2C_253/2012 du 11 janvier 2013 consid. 4), pour que le parent étranger puisse lui-même prétendre à un droit de séjour en Suisse sur la base de l'ALCP.
3.3. Aux termes de l'art. 43 al. 1 LEtr, le conjoint étranger du titulaire d'une autorisation d'établissement ainsi que ses enfants célibataires étrangers de moins de 18 ans ont droit à l'octroi d'une autorisation de séjour et à la prolongation de sa durée de validité, à condition de vivre en ménage commun avec lui. En l'espèce, le recourant a divorcé d'une ressortissante italienne au bénéfice d'une autorisation d'établissement. Il ne peut se prévaloir de l'art. 43 LEtr.
3.4. Selon l'art. 50 al. 1 let. a LEtr, après dissolution de la famille, le droit du conjoint et des enfants à l'octroi d'une autorisation de séjour et à la prolongation de sa durée de validité en vertu des art. 42 et 43 LEtr subsiste si l'union conjugale a duré au moins trois ans et l'intégration est réussie. La période minimale de trois ans de l'union conjugale commence à courir dès le début de la cohabitation effective des époux en Suisse et s'achève au moment où ceux-ci cessent de faire ménage commun (<ref-ruling> consid. 4.1 p. 348; <ref-ruling> consid. 2 p. 231; <ref-ruling> consid. 3.3.3 p. 119). En l'espèce, le recourant s'est marié le 11 mars 2005 avec une ressortissante italienne au bénéfice d'une autorisation d'établissement et s'est séparé de celle-ci au mois d'août 2006, si bien que son union conjugale a duré moins de trois ans. Partant, il ne peut, ce qu'il ne fait d'ailleurs pas, se prévaloir de l'art. 50 al. 1 let. a LEtr.
4.
Il convient par conséquent d'examiner dans quelle mesure la poursuite du séjour du recourant en Suisse s'impose pour des raisons personnelles majeures au sens de l'art. 50 al. 1 let. b LEtr.
4.1. Selon l'art. 50 al. 1 let. b LEtr, après dissolution de la famille, le droit du conjoint et des enfants à l'octroi d'une autorisation de séjour et à la prolongation de sa durée de validité en vertu des art. 42 et 43 LEtr subsiste lorsque la poursuite du séjour du recourant en Suisse s'impose pour des raisons personnelles majeures. De telles raisons peuvent en particulier découler d'une relation digne de protection avec un enfant qui a le droit de séjourner en Suisse (cf. <ref-ruling> consid. 2.1 p. 318 s.; arrêt 2C_327/2010 du 19 mai 2011 consid. 2.2 i.f., non publié in <ref-ruling>). Dans ce cas, les conditions posées par l'art. 50 al. 1 let. b LEtr ne recoupent pas nécessairement celles de l'octroi d'une autorisation de séjour fondée sur l'art. 8 CEDH (arrêt 2C_411/2010 du 9 novembre 2010 consid. 5, non publié in <ref-ruling>). Le droit au respect de la vie familiale garantie par les art. 8 CEDH et 13 Cst. doit néanmoins être pris en compte dans l'application de l'art. 50 al. 1 let. b LEtr dont l'application ne saurait être plus restrictive que celle des art. 8 CEDH et 13 Cst. (cf. <ref-ruling> consid. 2.1 p. 318 s.; arrêts 2C_318/2013 du 5 septembre 2013 consid. 3.3; 2C_996/2011 du 28 juin 2012 consid. 2.1 et les références citées).
4.2.
4.2.1. Le parent qui n'a pas l'autorité parentale ni la garde de l'enfant ne peut d'emblée entretenir une relation familiale avec celui-ci que de manière limitée, en exerçant le droit de visite dont il bénéficie. Or, il n'est en principe pas nécessaire que, dans l'optique de pouvoir exercer son droit de visite, le parent étranger soit habilité à résider durablement dans le même pays que son enfant. Sous l'angle du droit à une vie familiale (cf. art. 8 par. 1 CEDH et art. 13 al. 1 Cst.), il suffit en règle générale que le parent vivant à l'étranger exerce son droit de visite dans le cadre de séjours de courte durée, au besoin en aménageant ses modalités quant à la fréquence et à la durée (cf. <ref-ruling> consid. 2.2 p. 319). Le droit de visite d'un parent sur son enfant ne doit en effet pas nécessairement s'exercer à un rythme bimensuel et peut également être organisé de manière à être compatible avec des séjours dans des pays différents (cf. arrêt 2C_1031/2011 du 22 mars 2012 consid. 4.2.3). Selon la jurisprudence constante du Tribunal fédéral, un droit plus étendu ne peut le cas échéant exister qu'en présence de liens familiaux particulièrement forts d'un point de vue affectif et économique, lorsque cette relation ne pourrait pratiquement pas être maintenue en raison de la distance qui sépare le pays de résidence de l'enfant du pays d'origine de son parent, et que l'étranger a fait preuve en Suisse d'un comportement irréprochable (cf. <ref-ruling> consid. 2.2 p. 319 et les arrêts cités).
4.2.2. L'exigence du lien affectif particulièrement fort doit être considérée comme remplie sur le plan affectif lorsque les contacts personnels sont effectivement exercés dans le cadre d'un droit de visite usuel selon les standards d'aujourd'hui, lorsque l'étranger détient déjà un droit de séjour en Suisse, de façon à prendre en compte l'art. 9 par. 3 de la Convention du 20 novembre 1989 relative aux droits de l'enfant (CDE; RS 0.107) sans toutefois déduire de dite convention une prétention directe à l'octroi d'une autorisation (<ref-ruling> consid. 2.4 et 2.5 p. 320 ss).
4.2.3. Selon la jurisprudence, on ne saurait parler de comportement irréprochable lorsqu'il existe, à l'encontre de l'étranger des motifs d'éloignement, en particulier si l'on peut lui reprocher un comportement répréhensible sur le plan pénal ou en regard de la législation sur les étrangers (arrêt 2C_762/2013 du 31 janvier 2014 consid. 5.1 i.f.). Par ailleurs, en droit des étrangers, le respect de l'ordre et de la sécurité publics ne se recoupent pas nécessairement avec la violation de dispositions pénales, de sorte que l'appréciation émise par l'autorité de police des étrangers peut s'avérer plus rigoureuse que celle de l'autorité pénale (cf. <ref-ruling> consid. 4.3 p. 150 s. et les références citées).
4.2.4. Il ressort de l'arrêt entrepris que le recourant n'a ni l'autorité parentale, ni le droit de garde sur son fils, ressortissant italien au bénéfice d'une autorisation d'établissement. Selon ses propres déclarations, le recourant n'a exercé son droit de visite que de manière restreinte jusqu'en 2011. Il n'a fourni aucune pièce à l'autorité précédente pour attester que, depuis 2011, son droit de visite sur son fils est exercé régulièrement. Il s'est contenté d'affirmer que cela était le cas et qu'il bénéficiait d'un droit de visite usuel. De plus, il ressort également de l'arrêt entrepris que s'il faut reconnaître au recourant une certaine implication financière envers son fils, il n'en demeure pas moins que le 24 mars 2010, la mère de ce dernier a été dans l'obligation de déposer une requête d'avis au débiteur auprès d'un tribunal civil. Les contributions d'entretien étaient en souffrance depuis le mois d'octobre 2009 et les paiements n'avaient repris qu'en février 2010, mais à concurrence d'un montant insuffisant. Le tribunal précité a ainsi invité l'employeur du recourant à prélever la contribution d'entretien directement sur le salaire de celui-ci. Il ressort finalement de l'arrêt contesté que le recourant a été condamné pour escroquerie, ayant perçu indument des prestations de l'assurance-chômage. De plus, au 20 janvier 2014, il faisait l'objet de 20 poursuites pour un montant total d'un peu moins de 21'700 fr. et de 17 actes de défaut de biens pour un montant total d'un peu moins de 35'900 fr.
Sur le vu des faits arrêtés par l'autorité précédente, on doit donc constater que le recourant, suite à sa séparation et jusqu'en 2011, c'est-à-dire durant près de cinq ans, n'a pas exercé son droit de visite de manière régulière. Outre ses propres déclarations et celles de son ancienne épouse, rien ne permet de retenir qu'il le fasse actuellement. Quand bien même il faudrait retenir que sur les quatre dernières années le droit de visite s'est déroulé normalement et à un rythme usuel, on devrait encore mentionner que ce n'est qu'après y avoir été contraint par une décision judiciaire que le recourant a finalement versé à son fils la contribution d'entretien à laquelle celui-ci a droit. Un tel comportement relativise fortement l'existence d'un lien familial économique particulièrement fort. En tout état de cause, la question de l'existence de liens familiaux particulièrement forts d'un point de vue affectif et économique peut être laissée indécise, puisque contrairement à ce que le recourant semble penser, son comportement n'est pas irréprochable. En effet, durant sa présence en Suisse, il a été condamné à 400 heures de travail d'intérêt général pour escroquerie. De plus, comme l'a retenu l'autorité précédente, dans le cadre de sa deuxième demande d'asile, le recourant n'était pas disposé à quitter le territoire helvétique, si bien que les autorités cantonales en charge de l'exécution de son renvoi ont dû s'adresser au Secrétariat d'Etat pour demander du soutien. Finalement, il faut constater que la situation financière du recourant est totalement obérée et qu'elle s'est nettement dégradée entre 2012 et 2014. Une telle situation exclut de considérer le comportement du recourant comme étant irréprochable (cf. arrêts 2C_427/2015 du 29 octobre 2015 consid. 4.5; 2C_420/2015 du 1 er octobre 2015 consid. 2.4). Contrairement à ce que celui-ci déclare, cette dégradation ne démontre pas sa bonne volonté à rembourser ses dettes. Au demeurant, le fait qu'il ait subit un accident et ait perçu des indemnités de l'assurance-accident et de l'assurance-chômage, comme il l'affirme, n'y change rien.
4.3. S'agissant de la réintégration sociale dans le pays de provenance, l'art. 50 al. 2 LEtr exige qu'elle semble fortement compromise (<ref-ruling> consid. 5.3 p. 4). La question n'est donc pas de savoir s'il est plus facile pour la personne concernée de vivre en Suisse, mais uniquement d'examiner si, en cas de retour dans le pays d'origine, les conditions de la réintégration sociale, au regard de la situation personnelle, professionnelle et familiale de l'étranger, seraient gravement compromises (cf. ATF <ref-ruling> consid. 3.3 p. 117).
En l'occurrence, le recourant n'a pas contesté l'appréciation faite à ce sujet par le Tribunal administratif fédéral. Ce dernier a notamment relevé à juste titre que le recourant avait vécu son enfance, son adolescence et une partie de sa vie d'adulte dans son pays d'origine. En outre, il y est retourné à deux reprises depuis qu'il est en Suisse. L'autorité précédente a également constaté que le recourant ne démontrait nullement qu'il pourrait se trouver dans une situation présentant des difficultés de réadaptation insurmontables en cas de retour dans ce pays, où se trouvent encore deux de ses enfants. Elle a en particulier mentionné que le recourant avait suivi une formation en République démocratique du Congo et qu'il y avait travaillé. Il ne présente pas de problème de santé. Compte tenu de ces éléments, l'autorité précédente pouvait retenir que la réintégration du recourant dans son pays d'origine ne serait pas fortement compromise.
4.4. Le recourant n'ayant durant de nombreuses années pas présenté de liens affectif et économique forts avec son fils, mais ne pouvant surtout pas se targuer d'un comportement irréprochable en Suisse, son retour en République démocratique du Congo n'étant au surplus pas gravement compromis, il ne saurait être question de violation de l'art. 50 al. 1 let. b LEtr et de l'art. 8 CEDH.
5.
En dernier lieu, hormis les liens du recourant avec son enfant, dont on a vu qu'ils ne justifient pas à eux seuls son séjour en Suisse, l'arrêt attaqué ne révèle aucun élément déterminant qui ferait apparaître le refus d'approuver la prolongation de l'autorisation de séjour du recourant comme disproportionné (cf. art. 96 LEtr). En tenant compte de l'âge d'arrivée en Suisse du recourant, de la durée et de la qualité de son séjour dans ce pays, du fait que son intégration professionnelle et socioculturelle en Suisse n'est pas particulièrement marquée, qu'il présente une situation financière obérée, des conséquences pour lui et son enfant d'un refus de demeurer en Suisse, de la possibilité de conserver des liens avec son fils en dépit de l'éloignement et des possibilités d'intégration à l'étranger où vivent deux de ses enfants, il faut constater que le refus d'approuver la prolongation de l'autorisation de séjour du recourant n'est pas une mesure disproportionnée.
6.
Les considérants qui précèdent conduisent au rejet du recours, dans la mesure où il est recevable. Les frais judiciaires sont mis à la charge du recourant (<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é dans la mesure où il est recevable.
2.
Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué au mandataire du recourant, au Secrétariat d'Etat aux migrations, au Tribunal administratif fédéral, Cour III, et au Service des migrations de la République et canton de Neuchâtel.
Lausanne, le 25 mai 2016
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Seiler
Le Greffier : Tissot-Daguette