Faits :
A.
Lors d'une audition devant la police en janvier 1996, A._, ressortissant kosovar né en 1974, a déclaré être arrivé en Suisse le 31 décembre 1991, pays qu'il n'a plus quitté depuis. Il n'aurait jamais travaillé en Suisse depuis son arrivée et logerait à U._, chez son frère.
Par décision du 12 mars 1996, l'Office de la population de la République et canton de Genève (ci-après: l'Office de la population) a prononcé à l'encontre de l'intéressé une décision de renvoi de Suisse, en application de l'art. 12 de l'ancienne loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (aLSEE; RO 49 279). Un délai au 31 juillet 1996 a en outre été fixé à A._ pour quitter le territoire. Consécutivement à cette décision, l'intéressé a déposé une demande d'asile le 7 août 1996. Celle-ci a été rejetée par l'Office fédéral des réfugiés (actuellement: l'Office fédéral des migrations; ci-après: l'Office fédéral) le 11 octobre 1996.
Lors d'une audition de police le 20 mai 2000, l'intéressé a en particulier déclaré avoir travaillé sans autorisation en Suisse.
B.
Le 22 avril 2005, l'intéressé a sollicité une autorisation de séjour et de travail. Le 2 juin 2005, l'Office de la population a délivré une autorisation révocable en tout temps, jusqu'à droit connu sur la demande d'autorisation de séjour. Il ressort de la notice d'entretien que l'intéressé est arrivé en Suisse le 5 août 1989 et qu'il n'a jamais quitté le pays, à l'exception d'une période de deux ans, de 2001 à 2003, affirmant être retourné au Kosovo. Le 27 mars 2006, l'Office de la population s'est déclaré disposé à délivrer une autorisation de séjour.
Le 17 mai 2006, l'Office fédéral a refusé d'approuver l'octroi d'une autorisation de séjour en faveur de l'intéressé. Par arrêt du 3 février 2009, le Tribunal administratif fédéral a confirmé ce prononcé. Un délai au 30 juin 2009 a été fixé à l'intéressé pour quitter la Suisse.
C.
Par acte du 31 janvier 2011, A._ a sollicité le réexamen de la décision prononcée le 17 mai 2006 à son encontre. A l'appui de sa demande, il a invoqué les démarches entreprises en décembre 2010 auprès des autorités compétentes en vue de l'obtention de la nationalité suisse et la réception de la documentation y relative, élément qui doit être assimilé, à son avis, à un préavis favorable de la part desdites autorités.
Par décision du 19 décembre 2011, l'Office fédéral a rejeté cette demande. Il a tout d'abord considéré que les éléments invoqués par l'intéressé constituaient un changement de circonstances postérieur à l'arrêt du 3 février 2009 et est entré en matière. Sur le fond, il a en particulier relevé que l'octroi d'une autorisation de séjour pour motifs individuels d'extrême gravité n'était pas destiné à permettre à des personnes séjournant clandestinement en Suisse d'y rester jusqu'à ce qu'ils remplissent les conditions pour déposer une demande de naturalisation. L'intéressé a recouru contre cette décision auprès du Tribunal administratif fédéral.
Dans un arrêt du 31 janvier 2014, le Tribunal administratif fédéral a rejeté le recours de A._. Il a en substance considéré que les démarches de l'intéressé tendant à obtenir la nationalité suisse ne constituaient pas un fait nouveau important susceptible d'entraîner un réexamen de la décision de l'Office fédéral en matière de refus d'exception aux mesures de limitation. Selon le Tribunal administratif fédéral, le dépôt d'une demande de naturalisation ne saurait pas justifier en lui-même l'octroi d'une autorisation de séjour en dérogation des conditions d'admission. Il a en outre constaté que l'intéressé se trouvait certes en Suisse depuis 22 ou 24 ans, mais que celui-ci était arrivé sans aucune autorisation de séjour et qu'il aurait dû quitter le pays au plus tard en juin 2009.
D.
Agissant par la voie du recours en matière de droit public, A._ demande au Tribunal fédéral, sous suite de dépens, outre l'effet suspensif, principalement d'annuler l'arrêt du Tribunal administratif fédéral du 31 janvier 2014 et d'ordonner à l'Office fédéral de lui octroyer une autorisation de séjour, subsidiairement de renvoyer la cause au Tribunal administratif fédéral pour instruction complémentaire et nouvelle décision. Il se plaint de violation de son droit d'être entendu, de violation de l'art. 15 de la loi fédérale du 29 septembre 1952 sur l'acquisition et la perte de la nationalité suisse (loi sur la nationalité; LN; RS 141.0) et de violation des art. 8 CEDH et 13 Cst.
Par ordonnance du 14 mars 2014, la 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 à prendre position. L'Office fédéral conclut au rejet du recours.

Considérant en droit :
1.
1.1. D'après l'art. 83 let. c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions en matière de droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral ni le droit international ne donnent droit. Selon la jurisprudence, il suffit, sous l'angle de la recevabilité, qu'il existe un droit potentiel à l'autorisation, étayé par une motivation soutenable, pour que cette clause d'exclusion ne s'applique pas et que, partant, la voie du recours en matière de droit public soit ouverte. La question de savoir si les conditions d'un tel droit sont effectivement réunies relève du fond (<ref-ruling> consid. 1.1 p. 179).
En l'occurrence, le recourant se prévaut en particulier des art. 8 CEDH et 13 Cst. (<ref-ruling> consid. 1d/aa p. 64 s.). Au regard des faits à la base de la présente cause, il est des plus douteux que le recourant puisse se prévaloir de ces normes. Au vu du sort réservé à la cause, cette question souffre toutefois de demeurer indécise au stade de la recevabilité. Dans cette mesure, il sera entré en matière sur le recours en matière de droit public.
1.2. En tant que le recourant invoque une violation de l'art. 15 LN, son recours en matière de droit public est en revanche irrecevable. Cette disposition concerne en effet la procédure de naturalisation ordinaire qui ne saurait faire l'objet d'un recours en matière de droit public au Tribunal fédéral (cf. art. 83 let. b LTF). A fortiori, le recours en matière de droit public est également irrecevable contre un prétendu droit à une autorisation de séjour qui en découlerait. A ce propos, il y a lieu ici de relever que, contrairement à l'avis du recourant, l'art. 15 LN ne donne, en tant que tel, aucun droit direct à une autorisation de séjour. C'est bien plus par le biais du cas individuel d'une extrême gravité prévu à l'art. 30 al. 1 let. b LEtr (cf. art. 13 let. f de l'ancienne ordonnance fédérale du 6 octobre 1986 limitant le nombre des étrangers [aOLE; RO 1986 1791] dont la portée était semblable; Marc Spescha, in Migrationsrecht, 3e éd. 2012, n° 5 ad art. 30 LEtr), comme le recourant l'a fait valoir devant le Tribunal administratif fédéral, qu'une autorisation de séjour pourrait éventuellement, dans de tels cas de figure et si les conditions sont remplies, être octroyée (cf. à propos de l'art. 13 let. f aOLE, arrêt 2A.317/2006 du 16 août 2006 consid. 4). La décision d'octobre 1995 rendue par le Département fédéral de justice et police, citée par le recourant dans son mémoire, fait d'ailleurs également référence à la notion de cas personnel d'extrême gravité de l'art. 13 let. f aOLE (cette décision faisant elle-même notamment référence aux arrêts 2A.61/1994 du 29 septembre 1994 et 2A.103/1990 du 16 juillet 1990). Comme le recourant n'invoque devant le Tribunal fédéral qu'une violation de l'art. 15 LN, à l'exclusion de l'art. 30 al. 1 let. b LEtr, et qu'au surplus l'invocation d'une violation de cette dernière disposition aurait aussi de toute façon dû être déclarée irrecevable (cf. arrêts 2C_614/2013 du 28 mars 2014 consid. 1.2; 2C_400/2011 du 2 décembre 2011 consid. 1.2.2), son recours, sur ce point, est irrecevable.
1.3. Pour le surplus, l'arrêt attaqué est une décision finale (art. 90 LTF), émanant du Tribunal administratif fédéral (art. 86 al. 1 let. a LTF) dans une cause de droit public (art. 82 let. a LTF). Déposé en temps utile (art. 100 al. 1 LTF) et dans les formes prescrites (art. 42 LTF) par le destinataire de l'acte attaqué qui a qualité pour recourir au sens de l'art. 89 al. 1 LTF, le recours en matière de droit public est par conséquent recevable.
2.
Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (cf. art. 105 al. 1 LTF). 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'art. 95 LTF, et si la correction du vice est susceptible d'influer sur le sort de la cause (art. 97 al. 1 LTF), ce que la partie recourante doit démontrer d'une manière circonstanciée, conformément aux exigences de motivation des art. 42 al. 2 et 106 al. 2 LTF (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).
Par conséquent, et même si le recourant affirme se référer intégralement aux faits retenus par l'instance précédente, en tant que celui-ci avance des éléments de fait ne ressortant pas de l'arrêt attaqué, sans exposer en quoi les conditions qui viennent d'être rappelées seraient réunies, il n'en sera pas tenu compte.
3.
En se fondant sur l'art. 29 al. 2 Cst., le recourant se plaint de la violation de son droit d'être entendu en ce que le Tribunal administratif fédéral a refusé d'administrer un moyen de preuve proposé. Il convient d'examiner en premier lieu ce grief d'ordre formel (<ref-ruling> consid. 5.1 p. 390).
3.1. 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. 5.2 p. 147 s.; <ref-ruling> consid. 2.1 p. 429).
3.2. En l'espèce, le recourant demandait l'audition d'un collaborateur du Service cantonal des naturalisations de la République et canton de Genève. Il voulait démontrer la pratique de ce service selon laquelle les formulaires et documents relatifs à la naturalisation ordinaire sont envoyés si le service estime que celui qui en fait la demande est " naturalisable ". Or, cette audition se rapporte exclusivement à la prétendue violation de l'art. 15 LN qui n'a pas d'incidence sur l'issue de la cause (cf. consid. 1.2 ci-dessus); c'est par conséquent à tort que le recourant fait valoir une violation de son droit d'être entendu eu égard à ces faits et moyens de preuves. Le recours doit donc être rejeté sur ce point.
4.
Le litige porte en définitive sur la question de savoir si le recourant peut prétendre à une autorisation de séjour sur la base des art. 8 CEDH et 13 Cst. Celui-ci fait référence à ces dispositions (dont la portée est identique, <ref-ruling> consid. 8.3.2 p. 350; <ref-ruling> consid. 3.2 p. 172 ss et les références citées) en se prévalant aussi bien de la protection de sa vie privée que familiale.
4.1. Un étranger peut se prévaloir de la protection de la vie familiale découlant de l'art. 8 par. 1 CEDH (et de l'art. 13 al. 1 Cst.) à condition qu'il entretienne une relation étroite et effective (cf. <ref-ruling> consid. 5 p. 269) avec une personne de sa famille ayant le droit de résider durablement en Suisse (ce qui suppose que cette personne ait la nationalité suisse, une autorisation d'établissement en Suisse ou un droit certain à une autorisation de séjour en Suisse, cf. <ref-ruling> consid. 1.3.1 p. 145 s.). Les relations familiales qui peuvent fonder, en vertu de l'art. 8 par. 1 CEDH, un droit à une autorisation de police des étrangers sont avant tout les rapports entre époux ainsi qu'entre parents et enfants mineurs vivant ensemble (<ref-ruling> consid. 1d/aa p. 65). Enfin, un étranger majeur ne peut se prévaloir de cette disposition que s'il se trouve dans un état de dépendance particulier par rapport à des membres de sa famille résidant en Suisse en raison, par exemple, d'un handicap (physique ou mental) ou d'une maladie grave (<ref-ruling> consid. 2 p.13 s.; <ref-ruling> consid. 1e p. 261 et la jurisprudence citée). En l'espèce, le recourant, majeur, célibataire, sans enfant, ne peut pas invoquer les relations qu'il prétend entretenir avec ses frères, soeurs, neveux et nièces, avec lesquels il ne se trouve pas dans un état de dépendance particulier, pour poursuivre son séjour en Suisse.
4.2. Sous l'angle étroit de la protection de la vie privée, l'art. 8 CEDH n'ouvre le droit à une autorisation de séjour qu'à des conditions restrictives. L'étranger doit en effet établir l'existence de liens sociaux et professionnels spécialement intenses avec la Suisse, notablement supérieurs à ceux qui résultent d'une intégration ordinaire. Le Tribunal fédéral n'adopte pas une approche schématique qui consisterait à présumer, à partir d'une certaine durée de séjour en Suisse, que l'étranger y est enraciné et dispose de ce fait d'un droit de présence dans notre pays. Il procède bien plutôt à une pesée des intérêts en présence, en considérant la durée du séjour en Suisse comme un élément parmi d'autres. A ce propos, les années passées en Suisse en prison ne sont pas prises en considération, celles qui l'ont été dans l'illégalité ou au bénéfice d'une simple tolérance ne revêtent que peu de poids et ne sont par conséquent pas déterminantes (cf. <ref-ruling> consid. 4.2 p. 8; <ref-ruling> consid. 4.3 p. 23 s.). Dans le cas particulier, le recourant, qui a passé une partie non négligeable de sa vie dans l'illégalité ou au bénéfice d'une simple tolérance, ne démontre pas qu'il remplirait les conditions restrictives lui permettant d'invoquer le droit à la protection de la vie privée. Même s'il allègue une intégration plus qu'ordinaire et la création de liens particulièrement intenses avec la Suisse, rien dans l'arrêt attaqué ne permet de retenir l'existence de liens socio-professionnels qui dépasseraient ceux résultant d'une intégration normale. Son départ de Suisse ne le priverait pas d'une situation personnelle particulièrement enviable qu'il aurait pu se créer dans le canton de Genève.
4.3. Le recourant ne peut donc pas se prévaloir des art. 8 CEDH et 13 Cst., si bien que son recours doit aussi être rejeté sur ce point.
5.
Succombant, le recourant doit supporter un émolument judiciaire (art. 65 et 66 al. 1 LTF). Il ne sera 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, à l'Office fédéral des migrations, au Tribunal administratif fédéral, Cour III et à l'Office de la population de la République et canton de Genève.
Lausanne, le 18 juillet 2014
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Le Greffier :
Zünd Tissot-Daguette