Faits:
A. Le 23 mai 2001, A.X._, ressortissante camerounaise née Y._ en 1968, est entrée en Suisse et a déposé une demande d'asile. Lors de sa venue en ce pays, elle était accompagnée de l'une de ses filles, née le 8 avril 1991. Par décision du 23 juillet 2002, l'Office fédéral des réfugiés (devenu entre-temps Office fédéral des migrations, ci-après: ODM) a rejeté cette requête, prononcé le renvoi de Suisse de A.X._ et ordonné l'exécution de cette mesure. Le recours formé contre la décision précitée a été rejeté par la Commission suisse de recours en matière d'asile, par arrêt du 24 juin 2003.
A.X._ s'est mariée en 2005, à Emmen (LU) avec un citoyen suisse domicilié à Emmenbrücke (LU). A la suite de ce mariage, A.X._ a obtenu le 1er septembre 2006 une autorisation de séjour annuelle dans le canton de Lucerne au titre du regroupement familial; dite autorisation a été régulièrement renouvelée jusqu'au 1er septembre 2010. A.X._ aurait quitté le domicile conjugal le 16 septembre 2009. Par jugement du 5 mai 2010, le Tribunal du district de Hochdorf (LU) a prononcé le divorce du couple.
Le 29 octobre 2010, A.X._ a épousé, à Monthey (VS), B.X._, ressortissant suisse né en 1923. En raison de ce nouveau mariage, elle a sollicité le 19 novembre 2010 auprès des autorités compétentes du canton du Valais une autorisation de séjour dans le cadre du regroupement familial. B.X._ est toutefois décédé à Sion le 28 décembre 2010. Par courrier du 20 avril 2011, le Service de la population et des migrations du canton du Valais (ci-après: le Service cantonal) a informé A.X._ qu'au vu de son veuvage, il soumettait son dossier à l'ODM pour approbation, en vue de l'octroi d'une autorisation de séjour. Par décision du 4 août 2011, l'ODM a refusé ladite approbation et a imparti à A.X._ un délai au 31 octobre 2011 pour quitter le territoire suisse.
B. Par acte du 30 août 2011, A.X._ a recouru contre la décision précitée auprès du Tribunal administratif fédéral (ci-après: le TAF). Le TAF a rejeté le recours par décision du 12 juillet 2012, au motif que son mariage avec B.X._ n'avait duré que deux mois. Il a également nié l'existence de raisons personnelles majeures ou d'un droit fondé sur l'art. 8 CEDH. Il a cependant constaté qu'une procédure de prolongation d'une autorisation de séjour était formellement pendante devant les autorités compétentes du canton de Lucerne, dans le cadre de laquelle un droit fondé sur l'art. 50 al. 1 let. a LEtr en raison de son précédent mariage contracté le 23 décembre 2005 n'avait pas été tranché en raison d'une instruction incomplète.
C. A.X._ forme un recours en matière de droit public auprès du Tribunal fédéral, concluant principalement à l'annulation de la décision du TAF et à l'octroi, respectivement à la prolongation de son autorisation de séjour sous suite de frais et dépens. Elle a également conclu à l'octroi de l'effet suspensif et à la suspension de la procédure jusqu'à droit jugé dans le canton de Lucerne.
Par ordonnance présidentielle du 28 août 2012, l'effet suspensif a été attribué au recours.
Invités à déposer une réponse éventuelle, l'ODM a conclu au rejet du recours, tandis que le TAF a renoncé à se prononcer.

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. En l'espèce, divorcée d'un ressortissant suisse, la recourante a contracté un second mariage qui a pris fin avec le décès de son époux, de sorte qu'elle 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 la recourante. En pareilles circonstances, il convient d'admettre un droit de recourir sous l'angle de l'art. 83 let. c ch. 2 LTF, le point de savoir si c'est à juste titre que les autorités cantonales ont nié la réalisation des conditions de l'art. 50 LEtr ressortissant au fond et non à la recevabilité (cf. arrêts 2C_307/2012 du 26 juillet 2012; 2C_289/2012 du 12 juillet 2012; 2C_997/2011 du 3 avril 2012).
1.2 Pour le surplus, le recours est dirigé contre une décision finale (art. 90 LTF), rendue en dernière instance cantonale par un tribunal supérieur (art. 86 al. 1 let. d et al. 2 LTF); il a été formé en temps utile (art. 100 al. 1 LTF) et dans les formes prescrites (art. 42 LTF) par la destinataire de l'arrêt attaqué qui a un intérêt digne de protection à son annulation ou à sa modification (art. 89 al. 1 LTF). Par conséquent, il est en principe recevable en tant que recours en matière de droit public.
2. 2.1 Le recours peut être interjeté pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. Le Tribunal fédéral applique le droit d'office (art. 106 al. 1 LTF). Il n'est donc limité ni par les arguments soulevés dans le recours, ni par la motivation retenue par l'autorité précédente; il peut admettre un recours pour un autre motif que ceux qui ont été invoqués et il peut rejeter un recours en adoptant une argumentation différente de celle de l'autorité précédente (<ref-ruling> consid. 1.4 p. 400).
2.2 Le Tribunal fédéral statue en principe sur la base des faits établis par l'autorité précédente (art. 105 al. 1 LTF), sous réserve des cas prévus à l'art. 105 al. 2 LTF. Le recourant ne peut critiquer la constatation de faits importants pour le jugement de la cause que si ceux-ci ont été établis en violation du droit au sens de l'art. 95 LTF ou de manière manifestement inexacte (art. 97 al. 1 LTF), c'est-à-dire arbitraire, et si la correction du vice est susceptible d'influer sur le sort de la cause. La violation peut consister en un état de fait incomplet, car l'autorité précédente viole le droit matériel en n'établissant pas tous les faits pertinents pour l'application de celui-ci. L'appréciation des preuves est arbitraire lorsqu'elle est manifestement insoutenable, en contradiction avec le dossier, ou contraire au sens de la justice et de l'équité ou lorsque l'autorité ne tient pas compte, sans raison sérieuse, d'un élément propre à modifier la décision, se trompe sur le sens et la portée de celui-ci ou, se fondant sur les éléments recueillis, en tire des constatations insoutenables (<ref-ruling> consid. 4.1.2 p. 62).
En présence d'un état de fait manifestement inexact ou lacunaire, le Tribunal fédéral peut compléter ou rectifier d'office l'état de fait (cf. art. 105 al. 2 LTF). Toutefois, comme il est un juge du droit et non du fait, le complément ou la rectification des faits n'intervient que si le fait peut être déduit sans aucun doute possible des pièces du dossier. S'il apparaît qu'il faut compléter l'administration des preuves ou qu'il faut pour la première fois apprécier les preuves réunies, l'affaire devra être renvoyée à l'autorité précédente ou à l'autorité de première instance, conformément à l'art. 107 al. 2 LTF (cf. <ref-ruling> consid. 3.4.2 p. 295 s.; arrêt 2C_989/2011 du 2 avril 2012 consid. 3.1).
3. La recourante invoque en particulier la violation de l'art. 50 LEtr. Elle se plaint de l'établissement inexact des faits et de l'appréciation arbitraire des faits pertinents. Elle ne conteste pas que le mariage avec B.X._ n'a duré que quelques mois, mais déduit son droit à une autorisation de séjour de son union précédente, laquelle a duré plus de trois ans. Elle soutient qu'elle aurait dû obtenir une telle autorisation dans le canton de Lucerne si elle ne s'était pas rendue en Valais pour rejoindre son futur époux. Elle reproche au TAF de n'avoir pas examiné si les conditions donnant droit à la prolongation de son autorisation de séjour n'étaient pas d'ores et déjà réalisées avant son union avec B.X._.
3.1 Selon l'art. 42 al. 1 LEtr, le conjoint d'un ressortissant suisse a droit à l'octroi d'une autorisation de séjour et à la prolongation de sa durée de validité à condition de vivre en ménage commun avec lui. Ce droit subsiste après dissolution de la famille si l'union conjugale a duré au moins trois ans et l'intégration est réussie notamment (art. 50 al. 1 LEtr). Le titulaire d'une autorisation de séjour a le droit de déplacer son lieu de résidence dans un autre canton, pourvu qu'il ne soit pas au chômage et qu'il n'existe aucun autre motif de révocation au sens de l'art. 62 LEtr (art. 37 al. 1 et 2 LEtr). Le droit à l'autorisation de séjour est en effet valable dans toute la Suisse, et ne peut être limité ou révoqué par le déplacement du lieu de résidence de l'intéressé dans un autre canton (protégé par l'art. 13 al. 1 Cst.), dans lequel la poursuite du séjour lui serait refusée (cf. arrêt 2C_327/2010 du 19 mai 2011 consid. 2.1 non publié in <ref-ruling>).
3.2 En l'espèce, le TAF ne s'est pas prononcé sur les conditions formelles du changement de canton de résidence, mais au fond, sur le refus-même de la prolongation de l'autorisation de la recourante, qu'il a confirmé au motif que son deuxième mariage avait duré moins de trois ans. Il lui appartenait cependant de déterminer si la recourante avait un droit à cette autorisation en vertu de son précédent mariage. Le TAF a admis qu'une procédure était pendante devant les autorités compétentes du canton de Lucerne et considéré que la durée de l'union conjugale n'était pas établie, de sorte qu'il ne pouvait se prononcer sur la base des pièces du dossier. Faute d'établir ce fait pertinent pour décider du droit à une prolongation de l'autorisation de séjour de la recourante sur la base de l'art. 50 al. 1 let. a LEtr, l'instance précédente a violé le droit fédéral. Partant, il y a lieu d'admettre le recours.
Il sied de relever que le TAF a par ailleurs admis que la recourante a travaillé durant quelques années comme téléphoniste dans le canton de Lucerne, qu'elle a suivi à Berne un cours d'aide-soignante dispensé par la Croix-Rouge et a manifesté l'intention d'occuper à l'avenir un emploi dans ce dernier domaine. Au surplus, elle parle le français et l'allemand, n'a perçu aucune aide sociale de la part de la collectivité publique et n'a fait l'objet d'aucune condamnation pénale. Selon la jurisprudence, il faudrait de sérieux éléments pour nier, au sens de l'art. 50 al. 1 let. a LEtr, l'intégration réussie d'un étranger disposant d'un emploi stable, qui n'a jamais recouru aux prestations de l'aide sociale, qui n'a pas contrevenu à l'ordre public et qui maîtrise la langue parlée de son lieu de domicile (cf. arrêts 2C_749/2011 du 20 janvier 2012 consid. 3.2; 2C_427/2011 du 26 octobre 2011, consid. 5.3, 2C_430/2011 du 11 octobre 2011, consid. 4.2 et 2C_839/2010 du 25 février 2011, consid. 7.1.2).
3.3 L'arrêt attaqué ne comporte pas les éléments de fait suffisants pour que le Tribunal fédéral puisse vérifier si la recourante dispose d'un droit à une autorisation de séjour. Partant, il convient de renvoyer la cause au TAF, afin qu'elle examine ce point et statue à nouveau.
4. Dans ces conditions, il y a lieu d'admettre le recours dans la mesure où il est recevable, d'annuler la décision entreprise et de renvoyer la cause à l'autorité précédente, afin qu'elle complète l'instruction puis statue à nouveau dans le sens des considérants (cf. art. 107 al. 2 LTF).
Il n'y a pas lieu de percevoir de frais de justice (cf. art. 66 al. 4 LTF). Succombant, l'Office fédéral versera au recourant une indemnité à titre de dépens (cf. art. 68 al. 1 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis. L'arrêt du 12 juillet 2012 est annulé et la cause renvoyée au Tribunal administratif fédéral afin qu'il complète l'instruction et statue à nouveau dans le sens des considérants du présent arrêt.
2. Il n'est pas perçu de frais judiciaires.
3. L'Office fédéral des migrations versera à la recourante une indemnité de 2'000 fr. à titre de dépens.
4. Le présent arrêt est communiqué à la mandataire de la recourante, à l'Office fédéral des migrations et au Tribunal administratif fédéral, Cour III.
Lausanne, le 6 mars 2013
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
La Greffière: Cavaleri Rudaz