Faits: A. Le 1er octobre 2003, X._, ressortissant marocain né le *** 1976, a épousé A._, une compatriote, dans son pays d'origine. Le 13 mai 2007, il a rejoint son épouse, titulaire d'un permis de séjour puis d'établissement dès le 25 septembre 2007. Il a été mis au bénéfice d'un permis de séjour, dont il a requis la prolongation le 7 octobre 2009. Informé par la commune de B._ que A._ avait quitté le domicile conjugal pour s'installer à C._ le 3 novembre 2009, le Service de la population et des migrations (ci-après: le Service cantonal) a invité X._ à le renseigner sur sa situation matrimoniale et prolongé son autorisation de séjour jusqu'au 31 mars 2010. Cette demande est restée sans suite. Le 14 avril 2010, X._ a sollicité une nouvelle prolongation de son autorisation de séjour. Entendu le même jour par la police municipale de B._ sur requête du Service cantonal, il a expliqué que son couple connaissait des problèmes depuis le printemps 2008. Une procédure de divorce était engagée depuis le mois d'avril ou mai 2009 et les époux vivaient séparés depuis le mois de mai ou juin 2009. Son épouse, entendue par la police de C._ le 16 août 2010, a confirmé l'existence de problèmes conjugaux depuis le début de l'année 2008. La séparation remonterait au 1er mars 2008, date à laquelle elle était partie travailler dans le canton de Vaud. Elle estimait nulles les chances de réconciliation et avait entamé au Maroc des démarches en vue du divorce en mars 2009. B. Le 11 janvier 2011, le Service cantonal a refusé le renouvellement de l'autorisation de séjour de X._ et prononcé son renvoi de Suisse. Le 4 février 2011, X._ a déféré cette décision au Conseil d'État du canton du Valais, qui a rejeté ce recours le 4 avril 2012. X._ a recouru auprès du Tribunal cantonal du Valais (ci-après le Tribunal cantonal). Par arrêt du 4 octobre 2012, celui-ci a rejeté le recours. Il a retenu, en substance, qu'aucun reproche ne pouvait être formulé à l'encontre du Service cantonal qui avait agi avec la diligence requise, que X._ avait échoué à apporter la preuve du maintien d'une communauté familiale en dépit de domiciles séparés, que seule la durée de vie commune en Suisse devait être prise en compte dans le cadre de l'art. 50 al. 1 let. a LEtr, et enfin qu'aucune circonstance personnelle majeure n'imposait la poursuite du séjour dans notre pays. C. Le 9 novembre 2012, X._ a déposé un "recours" auprès du Tribunal fédéral à l'encontre de l'arrêt du 4 avril 2012. Il conclut à l'annulation de l'arrêt précité et à ce qu'il soit mis au bénéfice d'une prolongation de son autorisation de séjour, le tout sous suite de frais et dépens. Par ordonnance présidentielle du 14 novembre 2012, l'effet suspensif a été accordé au recours de X._. Le Service cantonal a renoncé à se prononcer, de même que le Tribunal cantonal. Le Conseil d'État a conclu au rejet du recours dans la mesure de sa recevabilité. Dans son préavis du 7 février 2013, l'Office fédéral des migrations propose le rejet du recours. 