Faits:
A. Après avoir divorcé de B.X._ en Macédoine, A.X._, ressortissant macédonien né en 1978, a épousé, en 2003, C._, ressortissante portugaise au bénéfice d'un permis d'établissement en Suisse. Le 10 octobre 2003, il a obtenu une autorisation de séjour CEE/AELE.
Par ordonnance pénale du 7 mars 2006, A.X._ a été condamné à dix jours d'emprisonnement avec sursis et 300 fr. d'amende pour faux dans les certificats parce qu'il avait fait usage d'un permis de conduire macédonien falsifié.
Le 18 avril 2007, le Tribunal de district de Sierre a autorisé les époux à vivre séparément. La séparation effective a eu lieu en fin avril 2007. Le 11 octobre 2007, l'intéressé a affirmé qu'il vivait de nouveau avec son épouse à Sierre. Son autorisation de séjour a été renouvelée le 6 décembre 2007. Les époux ont à nouveau vécu séparément dès mi-janvier 2008. S'estimant trompée, C._ a entamé une procédure de divorce.
Le 21 janvier 2009, le Service de la population du canton du Valais a communiqué à l'intéressé son intention de révoquer son permis de séjour. Le 16 février 2009, l'épouse de l'intéressé a affirmé que son époux entretenait toujours des relations avec B.X._ de laquelle il aurait eu un enfant né en 2005. Le 25 août 2009, l'intéressé a nié avoir avoir eu des relations extra-conjugales et exposé les liens qui l'unissent à la Suisse.
Par décision du 21 décembre 2009, le Service de la population a révoqué le permis de séjour de A.X._. Bien que l'union conjugale avait duré environ quatre ans, l'intéressé ne pouvait se prévaloir d'une intégration réussie compte tenu notamment du fait qu'il était connu de l'office des poursuite et que son comportement n'était pas exempt de tout reproche. L'intéressé a interjeté recours contre cette décision auprès du Conseil d'Etat du canton du Valais.
Le divorce a été prononcé le 1er mars 2010.
Le 21 juillet 2010, le frère de A.X._, en séjour illégal, a été contrôlé sur un chantier avec trois autres ressortissants macédoniens. Ils utilisaient une voiture que le patron de A.X._ avait prêtée à son frère.
Entendue le 4 août 2010 par la police, B.X._ a déclaré habiter chez A.X._ avec leur fille C._ née en 2005, être venue en Suisse avec ce dernier et y avoir séjourné du 12 janvier au 3 avril 2010, du 11 avril au 4 juillet 2010 et enfin depuis le 26 juillet 2010. Cette dernière et sa fille ont quitté la Suisse le 13 août 2010 par avion depuis Zurich où elles ont été conduites par A.X._.
Le 23 septembre 2010, la police a interpelé D._, ressortissante macédonienne entrée la veille en Suisse, chez A.X._ et trouvé sur place trois passeports dont celui du frère de l'intéressé qui était interdit de séjour en Suisse. La police a dénoncé A.X._ pour activités de passeur.
Le 5 avril 2011, le Conseil d'Etat a rejeté le recours au motif que l'intéressé n'avait pas eu la volonté effective de former une véritable union conjugale avec C._ en raison des relations extraconjugales qu'il avait entretenues avec B.X._ et qu'il n'était pas bien intégré en Suisse où il avait commis plusieurs infractions à la loi sur les étrangers. L'intéressé a interjeté recours contre la décision du 5 avril 2011 auprès du Tribunal cantonal du canton du Valais. Il a contesté avoir entretenu des relations extra conjugales avec B.X._ et l'avoir fait venir en Suisse. Il a affirmé avoir trouvé un travail depuis le mois de mai 2011 et faire partie des pompiers du Centre de secours incendie de Crans Montana comme cela ressortait de deux attestations.
B. Par arrêt du 30 septembre 2011, le Tribunal cantonal du canton du Valais a rejeté le recours. Les déclarations de C._ du 16 février 2009 selon lesquelles D._ avait 4 ans et que sa mère devait séjourner illégalement en Valais étaient confirmées par celles A.X._ avec qui elle était en contact depuis trois ans et chez qui elle habitait avec leur fille. Ces allégations étaient crédibles d'autant plus que l'intéressé avait amené D._ à l'aéroport. Il y avait ainsi de bonnes raisons d'admettre la paternité de l'intéressé, malgré les dénégations de ce dernier et l'absence de preuves scientifiques. Dans ces conditions, le Conseil d'Etat pouvait estimer que l'union conjugale était vidée de sa substance, à tout le moins dès le mois d'août 2004, de sorte que celle-ci n'avait pas duré au moins trois ans. Sur le plan de l'intégration, A.X._ était lié au séjour illégal de plusieurs compatriotes. Bien qu'il n'ait jamais été condamné à ce propos et qu'il ait toujours nié son implication, de sérieuses réserves pouvaient être émises sur son comportement et sur le respect de la sécurité et de l'ordre public suisse.
C. Agissant par la voie du recours en matière de droit public, A.X._ demande au Tribunal fédéral, sous suite de frais et dépens, d'annuler l'arrêt rendu le 30 septembre 2011 par le Tribunal cantonal du canton du Valais et de lui octroyer un permis de séjour.
Le Conseil d'Etat et le Tribunal cantonal du canton du Valais renoncent à déposer des observations.
Considérant en droit:
1. 1.1 En vertu de l'art. 83 let. c ch. 2 LTF, le recours 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, l'union conjugale du recourant avec une ressortissante portugaise ayant cessé d'exister, celui-ci ne peut pas déduire un droit à une autorisation de séjour de l'art. 43 al. 1 de la loi fédérale du 16 décembre 2005 sur les étrangers (LEtr, RS 142.20). Dans la mesure où le recourant soutient de manière plausible qu'il réalise les conditions de l'art. 50 al. 1 let. a LEtr, le recours en matière de droit public est en principe recevable. Le point de savoir si c'est à juste titre que l'instance précédente a nié la réalisation des conditions de l'art. 50 LEtr ressortit au fond et non à la recevabilité (cf. ATF 136 II 177 consid. 1.1 p. 179, 497 consid. 3.3 p. 500 s.).
1.2 Pour le surplus, le recours est dirigé contre une décision finale (art. 90 LTF), rendue par le Tribunal cantonal qui est une autorité supérieure de dernière instance cantonale (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 le 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).
2. 2.1 Saisi d'un recours en matière de droit public, le Tribunal fédéral se fonde sur les faits constatés par l'autorité précédente (cf. art. 105 al. 1 LTF). Selon l'art. 97 al. 1 LTF, le recours peut critiquer les constatations de fait à la double condition que les faits aient été établis de façon manifestement inexacte ou en violation du droit au sens de l'art. 95 LTF et que la correction du vice soit susceptible d'influer sur le sort de la cause, ce que le recourant doit rendre vraisemblable par une argumentation répondant aux exigences des art. 42 al. 2 et 106 al. 2 LTF (cf. ATF 136 II 508 consid. 1.2 p. 511). La notion de "manifestement inexacte" figurant à l'art. 97 al. 1 LTF correspond à celle d'arbitraire au sens de l'art. 9 Cst. A cet égard, 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. Il appartient à la partie recourante de démontrer le caractère arbitraire de la décision par une argumentation répondant aux exigences accrues de motivation de l'art. 106 al. 2 LTF (ATF 137 I 58 consid. 4.1.2 p. 6).
Enfin, le Tribunal fédéral examine librement la violation du droit fédéral (cf. art. 95 let. a et 106 al. 1 LTF), sous réserve des exigences de motivation figurant à l'art. 106 al. 2 LTF.
2.2 En l'espèce, le recourant propose au Tribunal fédéral sa propre présentation des faits en relation avec sa situation familiale, sociale et professionnelle. Dans les griefs relatifs à l'application du droit, il se borne ensuite à opposer sa version des faits à propos des relations extraconjugales qu'il nie avoir entretenues avec B.X._ et à propos de la paternité de l'enfant D._. Les affirmations du recourant ne répondent pas aux exigences de motivation de l'art. 106 al. 2 LTF. En effet, elles ne démontrent pas concrètement en quoi les faits auraient été établis et les preuves appréciées de manière arbitraire. Dans ces conditions, il n'est pas possible de s'écarter des constatations de faits de l'arrêt attaqué, notamment de la constatation que le mariage du recourant était dénué de toute substance à tout le moins à partir du mois d'août 2004.
3. 3.1 Selon l'art. 50 al. 1 let. a LEtr, après dissolution de la famille, le droit du conjoint à l'octroi d'une autorisation de séjour et à la prolongation de sa durée de validité en vertu des art. 42 et 43 LEtr subsiste si l'union conjugale a duré au moins trois ans et que l'intégration est réussie. Il s'agit de deux conditions cumulatives (ATF 136 II 113 consid. 3.3.3 p. 119). Le délai de trois ans de l'art. 50 al. 1 let. a LEtr se calcule en fonction de la durée pendant laquelle le couple fait ménage commun en Suisse (ATF 136 II 113 consid. 3.3.5 p. 120; arrêt 2C_735/2010 du 1er février 2011 consid. 4.1). La durée de trois ans vaut de façon absolue, quand bien même la fin de la vie conjugale serait intervenue quelques jours ou semaines seulement avant l'expiration de ce délai (arrêt 2C_735/2010 du 1er février 2011 consid. 4.1 et les arrêts cités).
3.2 En l'espèce, l'instance précédente a retenu d'une manière qui lie le Tribunal fédéral (art. 105 al. 1 LTF) et sans que les faits ne soient contestés d'une manière conforme aux exigences de motivation des art. 97 al. 1 et 106 al. 2 LTF (cf. consid. 2.3 ci-dessus) que l'union conjugale entre le recourant et C._ était vidée de toute substance à tout le moins à partir du mois d'août 2004. C'est par conséquent à bon droit qu'elle a jugé que le recourant ne remplissait pas la première condition liée à la durée de l'union conjugale de trois ans au moins prévue par l'art. 50 al. 1 let. a LEtr.
Dans ces conditions, le recours doit être rejeté dans la mesure où il est recevable sans qu'il soit nécessaire d'examiner si le recourant peut au surplus se prévaloir d'une intégration réussie.
4. Succombant, le recourant doit supporter les frais de la procédure fédérale (art. 66 al. 1 LTF). Il n'a pas droit à des dépens (art. 68 al. 2 LTF).
Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
3. Le présent arrêt est communiqué à la mandataire du recourant, au Service de la population et des migrations, au Conseil d'Etat et à la Cour de droit public du Tribunal cantonal du canton du Valais, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 2 juin 2012
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
Le Greffier: Dubey