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.
Considérant en droit:
1. Le Tribunal fédéral examine d'office et librement la recevabilité des recours qui lui sont soumis (art. 29 al. 1 LTF; cf. ATF 136 II 470 consid. 1 p. 472 et les arrêts cités).
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 dans le domaine du droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral ni le droit international ne donnent droit. Le recourant invoque le droit au respect de la vie familiale tel que protégé par l'art. 8 CEDH, puisqu'il vit avec son épouse, citoyenne suisse. Il se prévaut également de l'art. 42 al. 1 LEtr (RS 142.20) qui prévoit que le conjoint étranger 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 qui est son cas. Ces circonstances sont potentiellement de nature à lui conférer un droit à une autorisation de séjour. Il s'ensuit que le recours est recevable sous l'angle de l'art. 83 let. c ch. 2 LTF, étant précisé que le point de savoir si le recourant peut effectivement se prévaloir d'un tel droit relève du fond et non de la recevabilité (cf. ATF 137 I 284 consid. 1.3 p. 287).
1.2 Au surplus, déposé en temps utile (art. 100 al. 1 LTF) et dans les formes prescrites par la loi (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), le présent recours, dirigé contre une décision rendue par une autorité cantonale supérieure de dernière instance (art. 86 al. 1 let. d et al. 2 LTF), est en principe recevable.
1.3 En revanche, dans la mesure où le recourant demande à titre subsidiaire l'annulation de la décision du Service cantonal du 1er décembre 2011, son recours n'est pas recevable en raison de l'effet dévolutif complet du recours déposé auprès du Tribunal cantonal (cf. ATF 136 II 470 consid. 1.3 p. 474).
2. L'art. 99 al. 1 LTF dispose qu'aucun fait nouveau ni preuve nouvelle ne peut être présenté à moins de résulter de la décision de l'autorité précédente. Il y a lieu de se baser sur l'état de fait existant lors du prononcé de la décision attaquée (cf. arrêt 2C_537/2009 du 31 mars 2010 consid. 2.2.1). Le Tribunal fédéral doit en effet examiner si l'autorité précédente a correctement appliqué le droit. Or, la prise en compte d'une modification des circonstances conduirait à vider ce contrôle de son sens (cf. arrêt 2C_417/2008 du 18 juin 2010 consid. 2.1).
Au vu de ce qui précède, la Cour de céans ne tiendra pas compte du nouveau document déposé par le recourant par-devant le Tribunal fédéral, car il est postérieur à l'arrêt attaqué.
3. Saisi d'un recours en matière de droit public, le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (art. 105 al. 1 LTF), à moins que ces faits n'aient été établis de façon manifestement inexacte - ce qui correspond à la notion d'arbitraire (cf. pour cette notion ATF 136 III 552 consid. 4.2 p. 560; arrêt 2C_122/2012 du 1er novembre 2012 consid. 3.1) - ou en violation du droit (art. 105 al. 2 LTF). La partie recourante qui entend s'écarter des constatations de l'autorité précédente doit expliquer de manière circonstanciée en quoi les conditions d'une exception prévue par l'art. 105 al. 2 LTF seraient réalisées; à défaut, il n'est pas possible de tenir compte d'un état de fait qui diverge de celui contenu dans la décision attaquée. En particulier, le Tribunal fédéral n'entre pas en matière sur des critiques de type appellatoire portant sur l'état de fait ou sur l'appréciation des preuves (cf. ATF 137 II 353 consid. 5.1 p. 356).
Le recourant méconnaît à l'évidence ces principes. Il complète librement l'état de fait et ajoute des éléments postérieurs à l'arrêt attaqué. Il critique en outre l'appréciation des preuves effectuée par l'instance précédente sans exposer concrètement en quoi cette appréciation serait arbitraire ou manifestement inexacte, se contentant d'opposer sa propre appréciation des faits à la description retenue par le Tribunal cantonal. Une telle argumentation, caractéristique de l'appel, n'est pas admissible. Partant, l'Autorité de céans se limitera à examiner si le droit fédéral a été correctement appliqué par le Tribunal cantonal sur la base des faits ressortant de l'arrêt entrepris.
4. 4.1 En application de l'art. 42 al. 1 LEtr, le conjoint étranger 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. Après un séjour légal ininterrompu de cinq ans, le conjoint a droit à l'octroi d'une autorisation d'établissement (art. 42 al. 3 LEtr). Selon l'art. 51 al. 1 let. b LEtr, les droits prévus à l'art. 42 LEtr s'éteignent s'il existe des motifs de révocation au sens de l'art. 63 LEtr.
Aux termes de l'art. 63 al. 1 LEtr, l'autorisation peut être révoquée notamment lorsque l'étranger a fait de fausses déclarations ou a dissimulé des faits essentiels durant la procédure d'autorisation (art. 63 al. 1 let. a et 62 let. a LEtr) ou attente de manière très grave à la sécurité et l'ordre publics en Suisse ou à l'étranger, les met en danger ou représente une menace pour la sécurité intérieure ou extérieure de la Suisse (art. 63 al. 1 let. b LEtr).
Le Tribunal cantonal a considéré que le recourant remplissait les deux conditions précitées, ce que celui-ci conteste.
4.2 La jurisprudence considère comme essentiels, au sens de l'art. 62 let. a LEtr, en particulier les faits sur lesquels l'autorité a expressément demandé des précisions (cf. arrêt 2C_726/2011 du 20 août 2012 consid. 3.1.1). L'étranger est tenu d'informer l'autorité compétente de manière complète et conforme à la vérité sur tous les faits déterminants pour l'octroi de l'autorisation. Il importe peu que ladite autorité eût pu découvrir de tels faits par elle-même, si elle avait fait preuve de diligence (cf. arrêt 2C_456/2012 du 1er octobre 2012 consid. 3.1).
En l'espèce, le recourant a expressément répondu par la négative à la question figurant dans la demande d'autorisation qui portait sur les condamnations pénales dont il avait précédemment fait l'objet en Suisse. La dissimulation de tels faits suffit à réaliser le motif de révocation d'autorisation de l'art. 62 let. a LTF (cf. arrêt 2C_651/2009 du 1er mars 2010 consid. 4.1.1).
4.3 Selon la jurisprudence, attente de manière très grave à l'ordre public ou le met en danger au sens de l'art. 63 al. 1 let. b LEtr, l'étranger dont les actes lèsent ou compromettent des biens juridiques particulièrement importants, tels que l'intégrité corporelle, physique ou sexuelle. La gravité qualifiée de l'atteinte peut également être réalisée en cas de violation répétée, grave et sans scrupule de la sécurité et de l'ordre publics par des comportements relevant du droit pénal et montrant que l'étranger n'a ni la volonté ni la capacité de respecter à l'avenir le droit (cf. ATF 137 II 297 consid. 3.3 p. 303 s.; arrêt 2C_373/2012 du 28 septembre 2012 consid. 3.2). Pour évaluer la menace que représente un étranger condamné pénalement, le Tribunal fédéral se montre particulièrement rigoureux - en suivant en cela la pratique de la Cour européenne des droits de l'homme - en particulier en présence d'infractions à la législation fédérale sur les stupéfiants et d'actes de violence criminelle (arrêt 2C_401/2012 du 18 septembre 2012 consid. 3.3 et les arrêts cités).
En l'espèce, arrivé en Suisse à fin 2004 à l'âge de 18 ans, le recourant a été, dès 2006, condamné à sept reprises à des peines privatives de liberté successives qui, additionnées entre elles, atteignent trois ans. Tant la multiplication des infractions que la durée totale des condamnations pénales confirment la gravité des actes perpétrés par le recourant. Parmi les infractions retenues figurent en particulier des brigandages, séquestration et enlèvement, plusieurs infractions à la LStup (RS 812.121), ainsi que des infractions récurrentes contre le patrimoine (vols, recel, dommages à la propriété). Ni les jugements prononcés à son encontre ni la décision de renvoi du 16 septembre 2008 ne l'ont dissuadé de poursuivre ses activités délictueuses, sa dernière condamnation datant du 16 juillet 2010. Ainsi que le relève avec pertinence le Tribunal cantonal, c'est ainsi moins la gravité de chaque acte délictueux qui caractérise le comportement répréhensible du recourant que leur répétition, qui dénote son incapacité à se conformer au droit en vigueur. Les conditions objectives de révocation d'une autorisation de séjour telles que posées par l'art. 63 al. 1 let. b LEtr, sont ainsi remplies.
5. Le recourant soutient qu'il serait contraire à l'art. 8 CEDH de l'obliger à se séparer de son épouse, citoyenne suisse qui effectue une formation en Suisse et n'envisage pas de suivre son mari en Algérie.
5.1 Un étranger peut, selon les circonstances, se prévaloir de l'art. 8 par. 1 CEDH pour s'opposer à l'éventuelle séparation de sa famille. Pour qu'il puisse invoquer la protection de la vie familiale découlant de cette disposition, l'étranger doit entretenir une relation étroite et effective avec une personne de sa famille ayant le droit de résider durablement en Suisse (cf. ATF 137 I 284 consid. 1.3 p. 287).
Ces conditions sont remplies en l'espèce. En effet, selon l'état de fait retenu par l'instance précédente, non contesté sur ce point, le recourant vit en ménage commun avec son épouse, citoyenne suisse; en outre, il est admis que le lien conjugal entre les époux est réel.
5.2 Le droit au respect de la vie privée et familiale garanti par l'art. 8 par. 1 CEDH n'est toutefois pas absolu. Une ingérence dans l'exercice de ce droit est possible selon l'art. 8 par. 2 CEDH, pour autant qu'elle soit prévue par la loi et qu'elle constitue une mesure qui, dans une société démocratique, est nécessaire à la sécurité nationale, à la sûreté publique, au bien-être économique du pays, à la défense de l'ordre et à la prévention des infractions pénales, à la protection de la santé ou de la morale ou à la protection des droits et libertés d'autrui.
L'ingérence est en l'espèce prévue par le droit. En effet, le refus de prolonger l'autorisation de séjour du recourant est fondé sur l'art. 51 al. 1 let. b LEtr en relation avec l'art. 63 LEtr. En outre, il s'appuie sur l'art. 63 al. 1 let. b LEtr, disposition sanctionnant des comportements pénalement répréhensibles (cf. supra consid. 4.3).
6. 6.1 Encore faut-il, tant sous l'angle du droit interne que du droit conventionnel, que la révocation de l'autorisation fasse l'objet d'une pesée des intérêts et d'un examen de la proportionnalité (cf. art. 96 al. 1 LEtr et 8 par. 2 CEDH; ATF 135 II 377 consid. 4.3 p. 381).
Le fait de refuser un droit de séjour à un étranger dont la famille se trouve en Suisse peut entraver sa vie familiale et porter ainsi atteinte à l'art. 8 par. 2 CEDH (cf. ATF 135 I 153 consid. 2.1 p. 154 s.). Il n'y a toutefois pas atteinte à la vie familiale si l'on peut attendre des membres de la famille qu'ils réalisent leur vie de famille à l'étranger; l'art. 8 CEDH n'est a priori pas violé si le membre de la famille jouissant d'un droit de présence en Suisse peut quitter ce pays sans difficultés avec l'étranger auquel a été refusée une autorisation de séjour (cf. ATF 137 I 247 consid. 4.1.2 p. 249 s.). Pour apprécier ce qui est équitable, l'autorité doit notamment prendre en compte la nature et la gravité de l'infraction commise par l'intéressé, la durée de son séjour dans le pays d'où il va être renvoyé, la période qui s'est écoulée depuis la perpétration de l'infraction, ainsi que la conduite de l'intéressé durant cette période, la nationalité des diverses personnes concernées, la situation familiale de l'étranger, par exemple la durée de son mariage, et d'autres éléments dénotant le caractère effectif de la vie familiale d'un couple, le point de savoir si le conjoint était au courant de l'infraction au début de la relation familiale, la naissance d'enfants et, le cas échéant, leur âge. En outre, il y a lieu d'examiner l'ampleur des difficultés que risque de connaître le conjoint dans le pays d'origine de son époux ou épouse, bien que le simple fait qu'une personne se heurte à des obstacles en accompagnant son conjoint ne saurait en soi exclure un renvoi (cf. ATF 135 II 377 consid. 4.3 p. 381 s.; arrêt CourEDH Boultif c. Suisse du 2 août 2001, n° 54273/00, par. 48).
Quand le refus d'octroyer une autorisation de police des étrangers, respectivement sa révocation, se fonde sur la commission d'une infraction, la peine infligée par le juge pénal est le premier critère à utiliser pour évaluer la gravité de la faute et pour procéder à la pesée des intérêts en présence (cf. arrêt 2C_418/2009 du 30 novembre 2009 consid. 4.1). Selon la jurisprudence, en présence du conjoint étranger d'un ressortissant suisse, une condamnation à une peine privative de liberté supérieure à deux ans constitue la limite à partir de laquelle, en général, l'étranger qui n'a séjourné en Suisse que peu de temps ne saurait en principe bénéficier d'un titre de séjour en Suisse, même lorsqu'on ne peut pas ou difficilement exiger de son conjoint suisse qu'il quitte le pays (cf. ATF 135 II 377 consid. 4.3 p. 382 et les arrêts cités). Cette limite n'est pas absolue et a été fixée à titre indicatif; elle doit être appréciée au regard de toutes les circonstances du cas d'espèce, l'accumulation d'infractions permettant de s'éloigner de la limite des deux ans de détention (cf. arrêts 2C_265/2011 du 27 septembre 2011 consid. 6.2.5; 2C_915/2010 du 4 mai 2011 consid. 4). Doit également être pris en considération le fait que le conjoint, au moment du mariage, connaissait le passé criminel de la personne étrangère qu'il entendait épouser et devait par conséquent savoir qu'il risquait de ne pas pouvoir vivre sa vie maritale en Suisse (cf. arrêt 2C_141/2012 du 30 juillet 2012 consid. 6.3).
6.2 En l'espèce, le recourant a commis des infractions nombreuses et graves dont l'accumulation réalise les conditions de révocation d'une autorisation de séjour telles que posées par l'art. 63 al. 1 let. b LEtr (cf. supra consid. 4.3). Il est par ailleurs arrivé en Suisse à l'âge de 18 ans seulement, ayant vécu son enfance et son adolescence en Algérie. Il n'a en outre résidé en Suisse de manière légale que près de deux ans, les années passées dans l'illégalité ou en prison n'étant pas déterminantes dans la pesée des intérêts (cf. ATF 134 II 10 consid. 4.3 p. 23 s.). Les condamnations subies par le recourant totalisent près de 36 mois de privation de liberté. Elles s'étendent sur plusieurs années, la dernière remontant au 16 juillet 2010. En outre, le recourant ne peut se prévaloir d'une intégration professionnelle durable réussie puisqu'il n'a travaillé que durant de brèves périodes et n'a effectué aucune formation professionnelle. Le recourant s'est certes marié le 21 janvier 2011 avec une citoyenne suisse. En épousant le recourant, délinquant multirécidiviste qui a passé de nombreux mois en détention depuis le début de leur relation, l'épouse ne pouvait cependant ignorer le risque que celui-ci fasse l'objet d'une mesure d'éloignement la contraignant soit à suivre son conjoint soit à en vivre séparée. En outre, le couple n'a pas d'enfant. Dans ces conditions, la décision de l'instance précédente de confirmer la révocation de l'autorisation de séjour du recourant ne peut être qualifiée de disproportionnée.
7. Au vu de ce qui précède, les conditions de l'art. 63 al. 1 let. a et b LEtr étant réalisées, les droits du recourant prévus à l'art. 42 LEtr doivent être considérés comme éteints en application de l'art. 51 al. 1 let. b LEtr.
Le recours en matière de droit public doit par conséquent être rejeté dans la mesure où il est recevable.
Dans la mesure où ses conclusions apparaissaient dénuées de chances de succès, le bénéfice de l'assistance judiciaire doit être refusé au recourant (cf. art. 64 al. 1 LTF). Succombant, il supporte les frais judiciaires (art. 66 al. 1 LTF), qui seront toutefois fixés en tenant compte de sa situation financière, et n'a pas droit à des dépens (art. 68 al. 3 LTF).
Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. La demande d'assistance judiciaire est rejetée.
3. Les frais judiciaires, arrêtés à CHF 500.-, sont mis à la charge du recourant.
4. Le présent arrêt est communiqué à la mandataire du recourant, au Service de la population du canton de Vaud, au Tribunal cantonal du canton de Vaud, Cour de droit administratif et public, et à l'Office fédéral des migrations.
Lausanne, le 21 janvier 2013
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
La Greffière: Beti