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. 