Faits: A. X._, ressortissant algérien né en novembre 1987 en Algérie, est entré en Suisse en décembre 2004. Sous le nom de XA._, né en novembre 1988, il a déposé une demande d'asile. Le requérant ayant disparu, l'Office fédéral des migrations (ci-après l'Office fédéral) a prononcé la non-entrée en matière le 23 février 2005. Le 29 décembre 2005, X._ a déposé une nouvelle demande d'asile sous la même identité, qui a été radiée le 17 janvier 2006 après qu'il eût à nouveau disparu. Sous l'identité indiquée lors de son arrivée en Suisse, X._ a fait l'objet des condamnations pénales suivantes: Le 3 novembre 2006, condamnation à une peine de détention de 8 mois pour vol, vol en bande, brigandage, brigandage en bande, dommages à la propriété, contrainte, séquestration et enlèvement, violation de domicile, violence ou menace envers des autorités ou des fonctionnaires, violation d'une mesure de contrainte en matière de droit des étrangers, délit et contravention à la loi fédérale sur les stupéfiants. Le 5 juin 2007, condamnation à une peine privative de liberté de 30 jours pour violation d'une mesure de contrainte en matière de droit des étrangers et contravention à la loi fédérale sur les stupéfiants. Le 5 octobre 2007, condamnation à une peine privative de liberté de 160 jours pour vol, dommages à la propriété et séjour illégal. Le 4 septembre 2008, condamnation à une peine privative de liberté de 7 mois pour vol, violence ou menace envers des autorités ou des fonctionnaires, séjour illégal, violation d'une mesure de contrainte en matière de droit des étrangers, non-respect d'une assignation à un lieu de résidence, séjour illégal et contravention à la loi fédérale sur les stupéfiants. Le 14 avril 2009, condamnation à une peine privative de liberté de 6 mois pour vol, dommages à la propriété, violation de domicile, séjour illégal et contravention à la loi fédérale sur les stupéfiants. Le 3 septembre 2009, condamnation à une peine privative de liberté de 160 jours pour vol, dommages à la propriété, recel, violation de domicile et séjour illégal. Le 16 juillet 2010, condamnation à une peine privative de liberté de 90 jours pour tentative de vol, séjour illégal et contravention à la loi fédérale sur les stupéfiants. Le 16 septembre 2008, le Service de la population du canton de Vaud (ci-après le Service cantonal) a prononcé le renvoi de l'intéressé. En date du 21 avril 2010, X._ a sollicité l'octroi d'une autorisation de séjour en vue de mariage. Dans son rapport d'arrivée, il a mentionné son nom complet et sa véritable date de naissance. Il a en outre indiqué être entré en Suisse en juillet 2008, n'y avoir jamais séjourné auparavant et n'avoir fait l'objet d'aucune condamnation. Le 21 janvier 2011, il a épousé Y._, citoyenne suisse. A la suite de ce mariage, X._ a été mis au bénéfice d'une autorisation de séjour au titre du regroupement familial. B. Par courrier du 15 août 2011, le Service cantonal a informé X._ qu'il entendait révoquer son autorisation de séjour compte tenu des nombreuses condamnations pénales dont il avait fait l'objet ainsi que de la dissimulation de celles-ci lors de la procédure d'autorisation, et lui a donné l'occasion de se déterminer. Par décision du 1er décembre 2011, le Service cantonal a révoqué l'autorisation de séjour de X._ et prononcé son renvoi de Suisse. Le 3 février 2012, X._ a recouru contre cette décision au Tribunal cantonal du canton de Vaud, Cour de droit administratif et public (ci-après le Tribunal cantonal) qui, par arrêt du 9 août 2012, a rejeté ce recours. Les juges cantonaux ont retenu, en substance, que l'intéressé avait, par ses agissements, porté gravement atteinte à la sécurité et à l'ordre publics suisses, la répétition des actes délictueux dénotant son incapacité à se conformer au droit en vigueur. Ils ont également relevé que X._ n'avait pas fait état de ses condamnations lors de l'établissement de son rapport d'arrivée le 21 avril 2010. Enfin, le Tribunal cantonal a retenu que les liens unissant le recourant à son épouse ne l'emportaient pas sur son passé criminel et sur la dissimulation de ces faits essentiels à l'autorité, de sorte qu'il pouvait être astreint à poursuivre sa relation maritale depuis l'étranger. C. Par acte du 10 septembre 2012, X._ dépose un recours en matière de droit public au Tribunal fédéral. Sous suite de frais et dépens il conclut, à titre principal, à ce que l'arrêt du Tribunal cantonal du 9 août 2012 soit réformé dans le sens du maintien de son autorisation de séjour. A titre subsidiaire, il sollicite l'annulation de la décision du Service cantonal du 1er décembre 2011 et le renvoi du dossier à cette instance pour nouvelle décision dans le sens des considérants. Il requiert en outre le bénéfice de l'assistance judiciaire. Par ordonnance présidentielle du 14 septembre 2012, l'effet suspensif a été accordé au recours de X._. Le Service cantonal a renoncé à déposer une détermination. Le Tribunal cantonal s'est référé à l'arrêt attaqué. L'Office fédéral a proposé le rejet du recours. Par courrier du 15 octobre 2012, le recourant a déposé une pièce nouvelle et sollicité qu'il en soit tenu compte. 