Faits: A. X._, ressortissant serbe, né en 1973, s'est marié dans son pays d'origine, le 23 octobre 2003, avec une Suissesse, A._. Il est venu en Suisse le 9 avril 2004, au bénéfice d'une autorisation de séjour pour regroupement familial. L'épouse a quitté le domicile conjugal le 31 août 2005 pour aller vivre en France. Le 12 avril 2006, les époux ont signé une déclaration de ménage commun devant les autorités sierroises, qui a été renouvelée le 13 mars 2007. Le 14 avril 2006, ils ont informé les autorités cantonales qu'ils reprenaient la vie commune, de sorte que l'autorisation de séjour de X._ a été prolongée jusqu'au 8 avril 2008. A la fin du mois d'août 2007, A._ a adressé un courrier non daté à la police municipale de Sierre, dans lequel elle écrivait que son mariage « était un mariage blanc, un mariage pour de l'argent ». Entendu le 7 octobre 2007 par la police de Sierre, X._ a contesté avoir versé de l'argent à son épouse pour leur mariage ou l'avoir intimidée en vue d'obtenir la prolongation de son autorisation de séjour et a admis que leur séparation datait du mois d'août 2007. B. Par décision du 3 novembre 2008, le Service de la population et des migrations du canton du Valais (ci-après: le Service de la population) a rejeté la demande de prolongation de l'autorisation de séjour de X._ et a prononcé son renvoi de Suisse. Durant la procédure de recours auprès du Conseil d'Etat du canton du Valais, A._ a été entendue par le Service de la population. Elle a contesté être l'auteur de la lettre reçue le 29 août 2007 par la police municipale de Sierre, mais a confirmé qu'il s'agissait d'un mariage blanc et qu'elle n'avait jamais vécu avec son mari. Le 23 décembre 2009, le Conseil d'Etat a admis le recours de X._, en considérant que son autorisation de séjour pouvait être prolongée pour « raisons personnelles majeures » au sens de l'art. 50 al. 1 let. b de la loi fédérale sur les étrangers (LEtr; RS 142.20). Partant, le Service de la population a informé l'intéressé, le 19 janvier 2010, qu'une telle autorisation lui serait délivrée, sous réserve de l'approbation de l'autorité fédérale. C. Par décision du 30 mars 2010, l'Office fédéral des migrations (en abrégé: ODM) a refusé de donner son approbation à l'autorisation de séjour en faveur de X._ et a prononcé son renvoi de Suisse. Saisi d'un recours de l'intéressé contre cette décision, le Tribunal administratif fédéral l'a rejeté, par arrêt du 17 février 2012. Il a retenu en bref que que l'union conjugale ayant duré moins de trois ans, X._ ne pouvait obtenir une autorisation de séjour sur la base de l'art. 50 al. 1 let. a LEtr. En outre, rien ne permettait de conclure à l'existence de raisons personnelles majeures au sens de l'art. 50 al. 1 let. b LEtr. D. Agissant par la voie du recours en matière de droit public, X._ conclut, sous suite de frais et dépens, à l'annulation de l'arrêt du Tribunal administratif fédéral du 17 février 2012 et au renouvellement de son autorisation de séjour. Le Tribunal administratif fédéral a renoncé à se déterminer sur le recours et l'ODM propose de le rejeter. Par ordonnance présidentielle du 2 avril 2012, l'effet suspensif a été attribué au recours.