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.

Considérant en droit:
1. Le litige porte sur le refus d'approuver la prolongation de l'autorisation de séjour du recourant. A juste titre, la décision de renvoi prononcée par les autorités fédérales n'est pas remise en cause dans le recours, car cette question tranchée par le Tribunal administratif fédéral ne peut être revue par le Tribunal fédéral (art. 83 let. c ch. 4 et 113 LTF).
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. En l'espèce, la vie conjugale du recourant avec une ressortissante suisse ayant cessé, celui-ci ne peut pas déduire un droit à une autorisation de séjour de l'art. 42 al. 1 LEtr, ni de l'art. 49 LEtr. Reste l'art. 50 al. 1 LEtr qui subordonne la prolongation de son autorisation de séjour à certaines conditions dont se prévaut le recourant. Dans la mesure où il reproche à l'autorité fédérale de ne pas avoir retenu de circonstances propres à lui conférer un droit de demeurer en Suisse au sens de cette disposition, le recours est recevable, le point de savoir si les conditions posées par la loi sont effectivement réunies relève en effet de l'examen au fond (cf. arrêts 2C_304/2009 du 9 décembre 2009 consid. 1.1, non publié in <ref-ruling>, 2C_460/2009 du 4 novembre 2009, consid. 2.1.1 non publié aux <ref-ruling> et 2C_236/2011 du 2 septembre 2011 consid. 1.3).
1.2 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 une décision du Tribunal administratif fédéral (<ref-law>), est en principe recevable.
2. Le Tribunal fédéral fonde son raisonnement juridique sur les faits constatés par l'autorité précédente (<ref-law>), à moins que ces faits n'aient été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire (<ref-ruling> consid. 4.1.2 p. 62; <ref-ruling> consid. 4.3 p. 62) - ou en violation du droit au sens de l'<ref-law> (cf. <ref-law>). Si le recourant entend s'écarter des constatations de fait de l'autorité précédente (cf. <ref-law>), il doit expliquer de manière circonstanciée en quoi les conditions d'une exception prévue par l'<ref-law> seraient réalisées. Sinon, il n'est pas possible de tenir compte d'un état de fait divergent de celui qui est contenu dans l'acte attaqué (cf. <ref-ruling> consid. 5.1 p. 356; <ref-ruling> consid. 3 p. 104).
3. 3.1 Selon l'art. 50 al. 1 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 subsiste si l'union conjugale a duré au moins trois ans et l'intégration est réussie (let. a). L'existence d'une véritable union conjugale suppose que que la relation entre époux soit effectivement vécue et que ces derniers aient la volonté de la maintenir (<ref-ruling> consid. 3.1.2 p. 347, confirmé récemment in arrêt 2C_821/2011 du 26 juin 2012, consid. 2, destiné à la publication). Pour cela il faut se baser essentiellement sur la durée pendant laquelle le couple a fait ménage commun en Suisse (<ref-ruling> consid. 3.3.5 p. 120).
3.2 Il est en l'espèce établi que les époux X._-A._ sont arrivés en Suisse le 9 avril 2004 et qu'ils se sont définitivement séparés à la fin du mois d'août 2007. Contrairement à ce que soutient le recourant cette durée de plus de trois ans ne saurait être prise en considération, dès lors que son épouse a quitté une première fois le domicile conjugal du 31 août 2005 au 12 avril 2006 pour aller vivre chez sa mère en France, sans qu'elle puisse se prévaloir de l'exception à l'exigence du ménage commun prévue par l'art. 49 LEtr (cf. arrêt précité 2C_821/2011 du 26 juin 2012, consid. 2). Les arguments que le recourant présente pour justifier le maintien de la communauté conjugale pendant cette période sont dépourvus de tout fondement au vu des déclarations de l'épouse, de sorte que le Tribunal fédéral peut, sur ce point, se rallier aux motifs retenus dans l'arrêt attaqué (cf. consid. 4.2 et 6.1.1). C'est donc sans arbitraire que les premiers juges ont considéré que les conjoints n'avaient vécu ensemble que du 9 avril 2004 au 30 août 2005, puis du 12 avril 2006 à fin août 2007, soit pendant environ deux ans et neuf mois.
3.3 Il s'ensuit que l'art. 50 al. 1 let. a LEtr n'est pas applicable, l'union conjugale ayant duré moins de trois ans. Les conditions posées par cette disposition étant cumulatives (<ref-ruling> consid. 3.3.3 p. 119), il n'y pas lieu d'examiner au surplus si l'intégration est réussie. L'argumentation du recourant sur son « intégration parfaite » en Valais n'entre donc pas en considération dans ce contexte qui n'a d'ailleurs pas non plus été examiné par le Tribunal administratif fédéral. Reste à déterminer si le recourant peut se prévaloir de raisons personnelles majeures au sens de l'art. 50 al. 1 let. b LEtr pour obtenir une autorisation de séjour sur la base de cette disposition.
4. 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é subsiste si la poursuite du séjour en Suisse s'impose pour des raisons personnelles majeures. L'art. 50 al. 1 let. b et al. 2 LEtr vise à régler les situations qui échappent aux dispositions de l'art. 50 al. 1 let. a LEtr, soit parce que le séjour en Suisse durant le mariage n'a pas duré trois ans ou parce que l'intégration n'est pas suffisamment accomplie ou encore parce que ces deux aspects font défaut mais que - eu égard à l'ensemble des circonstances - l'étranger se trouve dans un cas de rigueur après la dissolution de la famille (<ref-ruling> consid. 3.2.1 p. 348; <ref-ruling> consid. 4.1 p. 7). A cet égard, c'est la situation personnelle de l'intéressé qui est décisive et non l'intérêt public que revêt une politique migratoire restrictive. Par conséquent, il y a lieu uniquement de décider du contenu de la notion juridique indéterminée "raisons personnelles majeures" et de l'appliquer au cas d'espèce, en gardant à l'esprit que l'art. 50 al. 1 let. b LEtr confère un droit à la poursuite du séjour en Suisse, contrairement à l'art. 30 al. 1 let. b LEtr (<ref-ruling> consid. 3.2.1 p. 348; <ref-ruling> consid. 3 et les références citées). Comme il s'agit de cas de rigueur survenant à la suite de la dissolution de la famille, en relation avec l'autorisation de séjour découlant du mariage, les raisons qui ont conduit à sa dissolution revêtent par conséquent de l'importance. L'admission d'un cas de rigueur personnel survenant après la dissolution de la communauté conjugale suppose que, sur la base des circonstances d'espèce, les conséquences pour la vie privée et familiale de la personne étrangère liées à ses conditions de vie après la perte du droit de séjour découlant de la communauté conjugale (art. 42 al. 1 et 43 al. 1 LEtr) soient d'une intensité considérable (<ref-ruling>). Le Tribunal fédéral a mis en lumière un certain nombre de situations dans lesquelles la poursuite du séjour en Suisse peut s'imposer, qui ne sont toutefois pas exhaustives (<ref-ruling> consid. 5.2 p. 3 ss). Parmi celles-ci figurent notamment les violences conjugales (art. 50 al. 2 LEtr), qui doivent revêtir une certaine intensité (<ref-ruling> consid. 5.3 p. 4), la réintégration fortement compromise dans le pays d'origine et le cas dans lequel le conjoint duquel dépend le droit de séjour de l'étranger décède (<ref-ruling> consid. 3.2.2 p. 349; <ref-ruling> consid. 5.3 p. 4; jurisprudence confirmée récemment in arrêt 2C_993/2011 du 10 juillet 2012, consid. 3.1, destiné à la publication).
4.2 Dans le cas du recourant, au vu des relations qu'il a entretenues avec son épouse, seules les difficultés de réintégration dans son pays d'origine pourraient justifier l'octroi d'une autorisation de séjour pour raisons personnelles majeures. A cet égard, l'intéressé relève qu'il a maintenant plus d'attaches en Suisse que dans son pays d'origine, dès lors que, divorcé de sa première épouse demeurée en Serbie, il ne voit qu'à de rares occasions ses enfants, actuellement âgés de douze et quinze ans, dont la mère a la garde. En revanche, il entretient des contacts réguliers avec ses parents, ses deux frères et leurs enfants, tous domiciliés à Sierre, ainsi qu'avec ses oncles et leurs familles qui se trouvent à Sion. Pour le reste, il se prévaut de son intégration socio-professionnelle, de sa connaissance du français, de son indépendance économique ou de sa participation à une équipe de football, soit d'éléments qui ne sont pas significatifs pour juger si, dans son pays d'origine, sa réintégration serait gravement compromise. Il ne s'agit en effet pas de savoir si la vie du recourant serait plus facile en Suisse (arrêt précité 2C_821/2011, consid. 3.1 i.f., destiné à la publication), mais uniquement de savoir si un retour en Serbie, où il a vécu jusqu'à l'âge de trente et un ans, entraînerait pour lui des difficultés de réadaptation insurmontables. Or, le recourant ne démontre nullement qu'il pourrait se trouver dans une telle situation, mais fait uniquement valoir les avantages qu'il aurait à poursuivre sa vie en Suisse, ce qui ne suffit pas pour admettre l'existence de raisons personnelles majeures.
4.3 Au vu des conditions strictes posées par la jurisprudence dans l'application de l'art. 50 al. 1 let. b et al. 2 LEtr, le Tribunal administratif fédéral a retenu à bon droit que le recourant ne pouvait pas se prévaloir de cette disposition pour obtenir la prolongation de son autorisation de séjour.
5. Compte tenu de ce qui précède, le recours doit être rejeté, avec suite de frais à la charge du recourant (<ref-law>). Il n'y a pas lieu d'allouer de dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
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 et au Tribunal administratif fédéral, Cour III.
Lausanne, le 26 juillet 2012
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
La Greffière: Rochat