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. 