Faits: A. X._ (ci-après: l'intéressé), ressortissant algérien né le ***1962, est entré en Suisse le 6 avril 1990 et y a résidé sans autorisation jusqu'en janvier 1991. Ayant épousé A._, ressortissante helvétique, le 1er février 1991, il a obtenu une autorisation de séjour par regroupement familial, laquelle a été régulièrement prolongée jusqu'au 1er février 1994. Ce premier mariage a été dissous par le divorce en date du 17 mars 1994, le couple étant néanmoins séparé depuis le mois de mai 1993. B. Eu égard à la nouvelle situation matrimoniale de l'intéressé, l'Office de la population de la République et canton de Genève (ci-après: l'Office cantonal de la population) a informé l'intéressé de son intention de ne pas renouveler ladite autorisation. Ce dernier ayant toutefois contracté un nouveau mariage le 23 septembre 1994 avec une autre citoyenne suisse, B._, l'Office cantonal de la population lui a délivré un nouveau titre de séjour en décembre 1994. Cette seconde union s'est également soldée par un divorce, lequel a été prononcé le 3 septembre 1998. La cessation de la vie commune remontait déjà au 1er mars 1996. Le 1er décembre 1998, l'Office cantonal de la population a refusé de renouveler le permis de séjour de l'intéressé, décision dont il s'est plaint devant la Commission cantonale de recours de police des étrangers. Par décision du 21 mars 2000, cette dernière a confirmé la décision de première instance. Un recours ultérieur auprès du Tribunal fédéral a été déclaré irrecevable le 21 août 2000, l'intéressé s'étant également fait impartir un délai pour quitter le territoire suisse au 29 octobre 2000. Il ne s'est pas soumis à cette injonction. Le 18 septembre 2001, X._ a épousé en troisièmes noces C._, ressortissante suisse. Son nouveau statut a débouché sur l'octroi d'une nouvelle autorisation de séjour le 26 juin 2002. L'intéressé a néanmoins quitté le domicile conjugal en septembre 2003 déjà, le couple étant alors séparé. Depuis le 20 mars 2006, les époux sont soumis à des mesures de protection de l'union conjugale. Aucune procédure de divorce n'a été entamée. C. Le 12 octobre 2006, l'Office fédéral des migrations a informé X._ de son intention de refuser d'approuver la prolongation de l'autorisation de séjour, en dépit du préavis favorable de l'Office cantonal de la population. Cette procédure a débouché sur une décision de l'Office fédéral des migrations de refuser d'approuver la prolongation de l'autorisation de séjour. En outre, en date du 28 décembre 2006, l'autorité fédérale a fixé à l'intéressé un délai de départ de Suisse au 22 mars 2007. A l'encontre de cette décision, l'intéressé a déposé un recours auprès du Tribunal administratif fédéral en date du 31 janvier 2007. Le 28 janvier 2010, le Tribunal administratif fédéral a rejeté ce recours. En substance, il a retenu qu'il était abusif de se prévaloir du mariage avec C._, dans la mesure où les époux étaient séparés depuis près de 7 ans, pour tenter d'obtenir une autorisation de séjour fondée sur le regroupement familial auquel l'art. 7 al. 1 de la loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (LSEE; RS 1 113) donne droit. Il a laissé ouverte la question de savoir si, conformément aux affirmations de C._, ce mariage n'était que de complaisance. Le Tribunal administratif fédéral a aussi nié le droit à une autorisation fondée sur l'art. 4 LSEE, les conditions autorisant l'administration à octroyer un titre de séjour fondé sur cette norme n'étant pas remplies. D. 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, d'annuler l'arrêt rendu le 28 janvier 2010 par le Tribunal administratif fédéral et de dire que l'Office fédéral des migrations ne pouvait pas lui refuser la prolongation de son autorisation de séjour. Il se plaint de la violation de l'art. 7 al. 1 LSEE. Il n'y aurait pas d'abus de droit à se prévaloir du mariage formel avec C._, en dépit de la durée de la séparation. Enfin, les conditions d'octroi d'une autorisation fondée sur l'art. 4 LSEE seraient réunies au regard de son intégration personnelle et professionnelle en Suisse. Le Tribunal administratif fédéral ne s'est pas prononcé. L'Office fédéral des migrations a conclu à son rejet.