Faits:
A. Par jugement du 21 septembre 2011, le Tribunal de police de l'arrondissement de la Côte a condamné X._ pour infraction à la loi fédérale sur le séjour et l'établissement des étrangers (LSEE) et infraction à la loi fédérale sur les étrangers (LEtr) à une peine de 90 jours-amende à 10 fr. le jour.
B. Le 28 janvier 2012, la Cour d'appel pénale du Tribunal cantonal vaudois a admis l'appel formé par le Ministère public et a condamné X._ pour infraction à la LSEE et infraction à la LEtr à une peine privative de liberté de 3 mois. En substance, il a été reproché à X._, ressortissant kosovar, d'avoir séjourné en Suisse sans autorisation entre le 1er novembre 2006 et le 25 mai 2011. Durant la même période, il a exercé, par intermittence, une activité lucrative sans autorisation auprès de vignerons et maraîchers. En 2007, il a fait venir son épouse du Kosovo alors qu'elle ne disposait d'aucune autorisation de séjour. Le casier judiciaire du recourant fait état de deux condamnations pour infraction à la réglementation sur le séjour des étrangers, l'une, en 2005, à 10 jours d'emprisonnement avec sursis (révoqué en 2006) et 500 fr. d'amende, l'autre, en 2006, à 15 jours d'emprisonnement et 500 fr. d'amende.
C. X._ forme un recours en matière pénale contre ce jugement. Il conclut, sous suite de frais et dépens, principalement, à la réforme de la décision entreprise en ce sens qu'il est condamné à une peine de 90 jours-amende à 10 fr. et, subsidiairement, à l'annulation du jugement et au renvoi de la cause à l'autorité précédente pour nouvelle instruction et nouveau jugement. Il sollicite par ailleurs l'assistance judiciaire.
Invités à déposer des observations sur le recours, la cour cantonale y a renoncé en se référant aux considérants de son jugement, cependant que le Ministère public a conclu à son rejet. X._ s'est déterminé sur ces écritures par courrier du 6 septembre 2012, lequel a été communiqué à titre de renseignement au Ministère public le 7 septembre 2012.

Considérant en droit:
1. Invoquant le principe de la lex mitior, le recourant prétend que l'autorité précédente ne pouvait pas le condamner à une courte peine privative de liberté. Son comportement ayant duré de novembre 2006 à mai 2011, les dispositions régissant pénalement le séjour illégal avaient successivement réglé le genre et la quotité de la peine de trois manières différentes. L'art. 23 al. 1 LSEE dans sa teneur jusqu'au 31 décembre 2006 punissait le séjour illégal de six mois d'emprisonnement, l'art. 23 al. 1 LSEE dans sa teneur du 1er janvier au 31 décembre 2007 de 180 jours-amende et l'art. 115 al. 1 LEtr, entré en vigueur le 1er janvier 2008, d'une peine privative de liberté d'un an au plus ou d'une peine pécuniaire. Selon le recourant, la cour cantonale aurait dû, en vertu du principe de la lex mitior, appliquer l'art. 23 al. 1 LSEE dans sa version du 1er janvier 2007 à l'ensemble des faits, le recourant ne pouvant ainsi être condamné qu'à des jours-amende.
1.1 Selon l'<ref-law>, la loi pénale ne s'applique qu'aux faits commis après son entrée en vigueur (principe de la non-rétroactivité de la loi pénale). Cependant, en vertu de l'<ref-law>, une loi nouvelle s'applique aux faits qui lui sont antérieurs si, d'une part, l'auteur est mis en jugement après son entrée en vigueur et si, d'autre part, elle est plus favorable à l'auteur que l'ancienne (exception de la lex mitior). Il en découle que l'on applique en principe la loi en vigueur au moment où l'acte a été commis, à moins que la nouvelle loi ne soit plus favorable à l'auteur. La règle de la lex mitior constitue une exception au principe de non-rétroactivité. Elle se justifie par le fait qu'en raison d'une conception juridique modifiée le comportement considéré n'apparaît plus ou apparaît moins punissable pénalement (<ref-ruling> consid. 6.1 p. 86 s.).
L'<ref-law> s'applique également au droit pénal accessoire, en vertu de l'<ref-law>, lorsqu'il ne dispose pas le contraire.
1.2 Une infraction est dite continue lorsque les actes créant la situation illégale forment une unité avec ceux qui la perpétuent, ou avec l'omission de la faire cesser, pour autant que le comportement visant au maintien de l'état de fait délictueux soit expressément ou implicitement contenu dans les éléments constitutifs du délit. Le délit continu se caractérise par le fait que la situation illicite créée par un état de fait ou un comportement contraire au droit se poursuit. Il est réalisé sitôt accompli le premier acte délictueux, mais n'est achevé qu'avec la fin ou la suppression de l'état contraire au droit (<ref-ruling> consid. 3.2 p. 9; <ref-ruling> consid. 3.1.2.2 p. 55).
Le séjour illégal est un délit continu (<ref-ruling> consid. 3.2 p. 9). L'infraction est achevée au moment où le séjour prend fin.
1.3 En matière de délit continu, la question du droit applicable se pose lorsque la loi change pendant l'exécution d'un tel délit. Un comportement qui n'était pas punissable sous l'ancien droit et qui le devient sous le nouveau sera jugé selon le nouveau droit, mais seule la partie du comportement postérieure à l'entrée en vigueur du nouveau droit sera punissable, conformément au principe de la non-rétroactivité. Si la nouvelle loi comporte uniquement une modification des sanctions, il n'est pas envisageable d'appliquer deux régimes de peine à un seul et même acte. Le délit continu constituant une unité, il n'est pas possible d'appliquer pour partie l'ancien et pour partie le nouveau droit. Le principe de la lex mitior ne permet en effet pas de combiner ancien et nouveau droit (<ref-ruling> consid. 6.2.3 p. 88 s.; <ref-ruling> consid. 3c p. 82). Pour régler cette question, la doctrine largement majoritaire propose l'application du nouveau droit à l'ensemble du délit continu, soit également à la partie antérieure à l'entrée en vigueur de la nouvelle norme (HURTADO POZO, Droit pénal, partie générale, 2009, p. 109 s.; repris par POPP/LEVANTE, in Basler Kommentar, Strafgesetzbuch I, 2e éd. 2007, no 6 ad <ref-law>; JEAN GAUTHIER, in Commentaire romand, Code pénal I, 2009, no 17 ad <ref-law>; STEPHAN TRECHSEL ET AL., Schweizerisches Strafgesetzbuch : Praxiskommentar, 2008, no 5 ad <ref-law>; DUPUIS ET AL., Code pénal, Petit commentaire, 2012, no 19 ad. <ref-law>). Dès lors qu'une norme abrogée ne peut être appliquée à un comportement postérieur à son abrogation et qu'il n'est pas possible d'appliquer pour partie l'ancien et pour partie le nouveau droit, la solution doctrinale se justifie. En cas d'aggravation de la sanction prévue par la loi, il convient toutefois, lors de la fixation de la peine, de tenir compte, dans un sens atténuant, du fait qu'une partie de l'infraction s'est déroulée pendant une période où la sanction était moins grave.
1.4 L'art. 115 al. 1 let. b LEtr punit celui qui séjourne illégalement en Suisse. Avant le 1er janvier 2008, date d'entrée en vigueur de la LEtr, ce comportement était réprimé par l'article 23 al. 1 LSEE. Les conditions de punissabilité n'ont pas changé, seul le type de peine et sa quotité maximale ont été modifiés. Ainsi, le nouveau droit est applicable à l'ensemble du comportement du recourant pour son séjour illicite de 2006 à 2011. C'est en vain que le recourant invoque la lex mitior à l'égard de sa condamnation en vertu de l'art. 115 al. 1 let. b LEtr.
1.5 Le recourant a non seulement été condamné en vertu de l'art. 115 al. 1 let. b LEtr, mais aussi de l'art. 115 al. 1 let. c, soit deux infractions distinctes. En application de l'art. 115 al. 1 let. c LEtr, celui qui déploie une activité lucrative illicite est punissable d'une peine privative de liberté d'un an au plus ou d'une peine pécuniaire. Avant l'entrée en vigueur de la LEtr, une telle activité était punie d'une amende jusqu'à 2000 fr. en vertu de l'art. 23 al. 6 LSEE.
Bien que la cour cantonale ne le dise pas expressément, on comprend de sa motivation qu'elle a considéré l'activité lucrative illicite du recourant comme un délit continu, à l'instar de l'infraction pour le séjour illégal réprimée par l'art. 115 al. 1 let. b LEtr. Ce point de vue ne peut être suivi. En effet, il ressort du jugement attaqué et du dossier que le recourant a travaillé, par intermittence, auprès de différents vignerons et maraîchers. Les interruptions de travail et la pluralité d'employeurs empêchent la qualification de délit continu. Le comportement du recourant constitue une succession de différents actes délictueux. Il incombera ainsi à la cour cantonale de déterminer quels actes délictueux ont été commis avant le 1er janvier 2008 et quels actes ont été commis après. En application de l'<ref-law>, les actes commis sous l'ancien droit devront être jugés selon ce droit (art. 23 al. 6 LSEE), qui est plus favorable que le nouveau puisque le comportement visé n'était punissable que d'une amende. En revanche, les actes commis sous l'empire du nouveau droit seront jugés en application de celui-ci. En fixant la peine, le juge aura égard à la question de la prescription s'agissant des contraventions à l'art. 23 al. 6 LSEE et, le cas échéant, à l'<ref-law> en application duquel des peines de genre différent doivent être prononcées cumulativement (<ref-ruling> consid. 4.3.1 p. 58).
2. Le recourant invoque une violation de la Directive du Parlement européen et du Conseil du 16 décembre 2008 relative aux normes et procédures communes applicables dans les Etats membres au retour des ressortissants de pays tiers en séjour irrégulier (Directive sur le retour 2008/115/CE), intégrée au droit suisse par l'arrêté fédéral du 18 juin 2010 (RO 2010 5925). Se référant à la jurisprudence de la Cour de justice de l'Union européenne (arrêt du 28 avril 2011 C-61/11 PPU El Dridi), il fait valoir que la cour cantonale ne pouvait pas le condamner dès lors que les dispositions pénales en cas de séjour illégal ne peuvent intervenir qu'en cas d'échec de la procédure administrative de renvoi.
2. Le recourant invoque une violation de la Directive du Parlement européen et du Conseil du 16 décembre 2008 relative aux normes et procédures communes applicables dans les Etats membres au retour des ressortissants de pays tiers en séjour irrégulier (Directive sur le retour 2008/115/CE), intégrée au droit suisse par l'arrêté fédéral du 18 juin 2010 (RO 2010 5925). Se référant à la jurisprudence de la Cour de justice de l'Union européenne (arrêt du 28 avril 2011 C-61/11 PPU El Dridi), il fait valoir que la cour cantonale ne pouvait pas le condamner dès lors que les dispositions pénales en cas de séjour illégal ne peuvent intervenir qu'en cas d'échec de la procédure administrative de renvoi.
2.1 2.1.1 Par accord du 26 octobre 2004, entré en vigueur le 1er mars 2008 (Accord entre la Confédération suisse, l'Union européenne et la Communauté européenne sur l'association de la Confédération suisse à la mise en ?uvre, à l'application et au développement de l'acquis de Schengen; RS 0.362.31, ci-après : AAS), la Suisse s'est engagée à mettre en ?uvre et appliquer l'acquis de Schengen. C'est ainsi que par arrêté fédéral du 18 juin 2010 (Arrêté fédéral portant approbation et mise en ?uvre de l'échange de notes entre la Suisse et la CE concernant la reprise de la Directive CE sur le retour [Directive 2008/115/CE]; RO 2010 5925), elle a repris la Directive sur le retour faisant partie de l'acquis de Schengen et modifié la LEtr (RS 142.20) et la loi fédérale sur l'asile (LAsi; RS 142.31) en conséquence.
2.1.2 La Directive sur le retour poursuit la mise en place d'une politique efficace d'éloignement et de rapatriement fondée sur des normes communes, afin que les personnes concernées soient rapatriées de façon humaine et dans le respect intégral de leurs droits fondamentaux ainsi que leur dignité (cf. Directive 2008/115/CE considérant 2).
Dans deux arrêts récents (arrêts du 28 avril 2011 C-61/11 PPU El Dridi et du 6 décembre 2011 C-329/11 Achughbabian), la Cour de justice de l'Union européenne (ci-après CJUE) a eu l'occasion d'examiner la compatibilité de législations prévoyant des peines privatives de liberté au seul motif de l'irrégularité de l'entrée ou du séjour d'un ressortissant d'un pays tiers. Dans les deux affaires, il s'agissait de personnes qui se trouvaient en séjour illégal dans le pays, Italie, respectivement France, et à l'encontre desquelles une procédure de refoulement avait été engagée. M. El Dridi ne s'était pas conformé à un ordre d'éloignement du 21 mai 2010. Il avait été condamné par le Tribunal di Trento à une peine d'un an d'emprisonnement pour ce motif en application du droit national. Se posait dès lors la question de la compatibilité de cette sanction qui visait le non-respect d'une des étapes de la procédure administrative de retour au regard des principes découlant de l'application de la Directive 2008/115/CE. M. Achughbabian, lui, ne s'était pas conformé à un arrêté lui faisant obligation de quitter le pays dans un délai d'un mois. Un arrêté de reconduite à la frontière et un arrêté de placement en rétention administrative avaient été prononcés contre lui. Le simple arrêté de reconduite à la frontière, fondé sur la constatation du délit de séjour irrégulier tel qu'il était défini par le droit national, était susceptible de conduire à une condamnation à une peine d'emprisonnement.
Dans les deux arrêts, la CJUE a relevé que la Directive sur le retour posait comme condition à l'adoption de mesures coercitives le respect des principes de proportionnalité et d'efficacité en ce qui concerne les moyens utilisés et les objectifs poursuivis. La CJUE en a déduit que les Etats membres ne pouvaient pas procéder à l'emprisonnement d'un ressortissant étranger en séjour irrégulier pour la seule raison qu'il continuait de se trouver de manière irrégulière sur le territoire de l'Etat après qu'un ordre de quitter le territoire national lui avait été notifié et que le délai imparti dans cet ordre avait expiré. En effet, selon la CJUE, une telle peine risquait de compromettre la réalisation de l'objectif poursuivi par ladite directive, à savoir l'instauration d'une politique efficace d'éloignement et de rapatriement des ressortissants de pays tiers en séjour irrégulier, notamment parce que le fait de condamner quelqu'un à une peine d'emprisonnement relativement longue avait nécessairement pour conséquence de retarder l'exécution de la décision de retour prise à son encontre. La CJUE a donc considéré que la Directive sur le retour, notamment ses articles 15 et 16, devait être interprétée en ce sens qu'elle s'opposait à une réglementation d'un Etat membre qui prévoyait le prononcé d'une peine d'emprisonnement à un ressortissant d'un pays tiers en séjour irrégulier pour le seul motif que celui-ci demeurait, en violation d'un ordre de quitter le territoire de cet Etat dans un délai déterminé, sur ledit territoire sans motif justifié. Autrement dit, selon la jurisprudence européenne, une peine d'emprisonnement pour séjour illégal ne peut être infligée à un ressortissant étranger que si la procédure administrative de renvoi a été menée à son terme sans succès et que le ressortissant étranger demeure sur le territoire sans motif justifié de non-retour. La CJUE a toutefois souligné que les ressortissants étrangers ayant, outre le séjour irrégulier, commis un ou plusieurs autres délits pouvaient, dans les hypothèses visées par l'art. 2 par. 2 let. b de la Directive sur le retour, c'est-à-dire en cas d'expulsion judiciaire prononcée comme sanction pénale ou de procédure d'extradition, être soustraits au champ d'application de ladite directive. A noter que cette dernière ne s'applique pas non plus aux personnes qui se sont vu refuser l'entrée dès la frontière extérieure Schengen et qui sont ensuite appréhendées sur le territoire d'un Etat Schengen, pas plus qu'en cas d'interdiction d'entrée à la frontière extérieure Schengen (art. 2 par. 2 let. a Directive sur le retour).
Les principes développés dans ces deux décisions ont été très récemment confirmés par la CJUE dans un arrêt du 6 décembre 2012 (C-430/11 Sagor). Dans cette affaire, M. Sagor séjournait en Italie sans avoir jamais eu de titre de séjour valable. Pour cette raison, il s'exposait à une condamnation pénale sous forme d'amende. La CJUE a précisé que la Directive sur le retour ne s'opposait pas à une poursuite pénale et à une condamnation à une peine pécuniaire réprimant le séjour irrégulier d'un ressortissant d'un Etat tiers, dès lors qu'une telle peine n'était pas de nature à retarder ou entraver la procédure de retour.
2.1.3 Contrairement à l'Accord du 21 juin 1999 sur la libre circulation des personnes (ALCP; RS 0.142.112.681), en particulier son art. 16 al. 2, l'AAS ne prévoit pas de reprise directe de la jurisprudence européenne. La Suisse, comme les autres parties, jouit de l'autonomie dans l'interprétation et l'application de l'acquis de Schengen. Toutefois, comme le rappelle le Conseil fédéral dans son message, il est dans l'intérêt de toutes les parties que les règles instaurées par Schengen soient interprétées et appliquées de manière identique de part et d'autre (Message du 1er octobre 2004 relatif à l'approbation des accords bilatéraux entre la Suisse et l'Union européenne, y compris les actes législatifs à la transposition des accords [« accords bilatéraux II »], FF 2004 5593 ss ch. 2.6.7.6). L'AAS a ainsi instauré un comité mixte qui a notamment pour mission d'observer l'application de cet accord par les différentes parties. S'il constate une différence substantielle dans l'interprétation et l'application de l'acquis de Schengen entre les autorités et juridictions suisses et la CJUE, il peut engager la procédure de règlement des différends prévue aux art. 9 al. 2 et 10 AAS qui peut aboutir, en cas d'échec, à la cessation de l'application de l'AAS.
En matière d'ALCP, l'art. 16 al. 2 de cet accord impose aux autorités suisses de tenir compte des arrêts de la CJUE antérieurs à sa signature. Toutefois, le Tribunal fédéral a précisé qu'afin de privilégier le parallélisme du système voulu par les Etats parties à l'ALCP, il n'y avait pas lieu de s'écarter de la jurisprudence de la CJUE, même postérieure à la signature de l'accord, sans raison valable (<ref-ruling> consid. 3.6.2 p. 15 s; <ref-ruling> consid. 3.1 p. 70 s.). En matière de droit privé, le Tribunal fédéral a également rappelé que lorsque l'ordre juridique suisse avait été adapté au droit européen, on ne devait pas uniquement viser une harmonisation dans l'adoption des règles, mais également dans leur interprétation et leur application (<ref-ruling> consid. 4.3.1 in fine p. 209 et les références citées).
Au vu de ce qui précède, le Tribunal fédéral n'est pas lié par les arrêts El Dridi, Achughbabian ou Sagor, même si une interprétation conforme du droit suisse doit être privilégiée (cf. ANDREAS ZÜND, in Migrationsrecht, 3e éd. 2012, no 12 ad. art. 115 LEtr). Toutefois, la question de l'éventuelle interprétation de l'art. 115 LEtr au regard de ces jurisprudences n'a pas à être examinée dans le présent contexte, dès lors que, pour les motifs qui vont suivre, le recourant ne se trouve pas dans les hypothèses visées par les arrêts européens.
2.2 Le recourant a été condamné à une peine privative de liberté de 3 mois pour avoir séjourné et travaillé illégalement en Suisse.
2.2.1 Sur le principe, la condamnation du recourant pour son activité lucrative illicite n'est pas critiquable. En effet, la Directive sur le retour ne concerne pas un tel comportement. Elle n'est ainsi pas applicable à cet aspect, pas plus que la jurisprudence précitée de la CJUE qui concerne uniquement la question du séjour illégal (cf. THOMAS HUGI YAR, Das Urteil El Dridi, die EU-Rückführungsrichtlinie und der Schengen-Besitzstand, Jusletter du 11 juillet 2011, no 11). La cour cantonale était donc fondée à condamner le recourant pour infraction à la réglementation sur les étrangers s'agissant de son activité lucrative sans autorisation. Il conviendra toutefois de tenir compte des éléments développés au considérant 1.5 supra s'agissant du droit applicable et de la fixation de la peine.
2.2.2 Pour ce qui est de son séjour illicite, le recourant ne se trouve pas dans la situation de l'étranger pour lequel aucune procédure de renvoi administratif n'a été menée à son terme sans succès. Il ressort des faits établis qu'il a déposé une demande d'asile qui a été rejetée en 2000. Invité à quitter le territoire suisse, il s'est caché. Il a été refoulé au Kosovo en 2001. Il a donc déjà fait l'objet des mesures coercitives visées par l'éloignement de l'art. 8 de la Directive 2008/115/CE concrétisée à l'art. 64 LEtr. Il est ensuite revenu en Suisse en 2003.
Le recourant ne saurait ainsi tirer argument de la jurisprudence de la CJUE concernant la Directive sur le retour, car sa situation n'est pas comparable à celles visées dans ces affaires. Il ne saurait en particulier être suivi lorsqu'il soutient que l'Etat doit à nouveau, à la suite de son retour, procéder à son renvoi forcé en utilisant la palette des mesures prévues par la Directive. En effet, la jurisprudence de la CJUE doit être interprétée dans ce sens qu'elle couvre tant l'hypothèse de la personne qui n'a en définitive pas pu être refoulée que celle qui l'a été et qui revient. Ce qui est déterminant, comme le retient l'arrêt Achughbabian, c'est que la personne à qui la procédure de retour a été appliquée, séjourne irrégulièrement sur le territoire sans motif justifié de non-retour. Aucun motif ne justifie de traiter moins bien le ressortissant qui est resté, parce qu'il s'est soustrait avec succès à une procédure de refoulement menée jusqu'à son terme, de celui qui a pu être refoulé, mais qui est revenu sur le territoire de l'Etat concerné. Dans les deux hypothèses, il faut retenir l'échec de la procédure de refoulement, quoique menée à son terme dans le respect des règles de fond et de forme. Le recourant n'invoque, par ailleurs, aucun motif justifié de non-retour. L'art. 115 LEtr peut donc lui être appliqué, car la peine n'est pas prononcée en cours ou avant une procédure de retour, mais après l'échec de celle-ci. La cour cantonale pouvait, par conséquent, condamner le recourant à une peine privative de liberté. Mal fondé, le grief doit être rejeté.
3. Le recourant invoque une violation de l'<ref-law>. Bien que le dossier soit renvoyé à l'autorité cantonale pour nouvelle fixation de la peine (cf. supra consid. 1.5), il convient, par économie de procédure, de relever les éléments suivants.
3.1 Aux termes de l'<ref-law>, le juge peut prononcer une peine privative de liberté ferme de moins de six mois uniquement si les conditions du sursis à l'exécution de la peine (<ref-law>) ne sont pas réunies et s'il y a lieu d'admettre que ni une peine pécuniaire, ni un travail d'intérêt général ne peuvent être exécutés.
A titre de sanctions, le Code pénal fait de la peine pécuniaire (<ref-law>) et du travail d'intérêt général (<ref-law>) la règle dans le domaine de la petite criminalité, respectivement de la peine pécuniaire et de la peine privative de liberté la règle pour la criminalité moyenne. Dans la conception de la partie générale du Code pénal, la peine pécuniaire constitue la sanction principale. Les peines privatives de liberté ne doivent être prononcées que lorsque l'Etat ne peut garantir d'une autre manière la sécurité publique. Quant au travail d'intérêt général, il suppose l'accord de l'auteur. En vertu du principe de la proportionnalité, il y a en règle générale lieu, lorsque plusieurs peines entrent en considération et apparaissent sanctionner de manière équivalente la faute, de choisir celle qui restreint le moins sévèrement la liberté personnelle de l'intéressé, respectivement qui le touche le moins durement. La peine pécuniaire et le travail d'intérêt général représentent des atteintes moins importantes et constituent ainsi des peines plus clémentes. Cela résulte également de l'intention essentielle, qui était au coeur de la révision de la partie générale du Code pénal en matière de sanction, d'éviter les courtes peines de prison ou d'arrêt, qui font obstacle à la socialisation de l'auteur, et de leur substituer d'autres sanctions. Pour choisir la nature de la peine, le juge doit prendre en considération l'opportunité de la sanction déterminée, ses effets sur l'auteur et son milieu social, ainsi que son efficacité préventive (<ref-ruling> consid. 4 p. 100 ss).
3.2 Il convient tout d'abord de déterminer si les conditions du sursis sont réalisées, première condition posée par l'<ref-law>. Cette question s'examine selon les critères de l'<ref-law> qui ont été rappelés dans l'arrêt publié aux <ref-ruling> consid. 2.1 p. 185 s., auquel il est renvoyé.
Le recourant a fait l'objet de deux condamnations pour infraction à la réglementation sur le séjour des étrangers, l'une, en 2005, à une peine de 10 jours d'emprisonnement avec sursis (révoqué en 2006) et 500 fr. d'amende, l'autre, en 2006, à 15 jours d'emprisonnement et 500 fr. d'amende. Il apparaît ainsi qu'une première condamnation avec sursis n'a pas dissuadé le recourant de maintenir son comportement contraire au droit. L'exécution d'une peine ferme n'a pas non plus dissuadé le recourant qui a persisté à rester et à travailler en Suisse, comportement qui fait l'objet de la présente procédure. Cela ne peut conduire qu'à un pronostic défavorable. Un sursis est exclu.
3.3 En second lieu, il convient de déterminer si une peine pécuniaire ou un travail d'intérêt général peuvent être exécuté, seconde condition posée par l'<ref-law>.
Selon les constations de la cour cantonale, le recourant ne dispose d'aucune autorisation de séjour ou de travail et son renvoi a été prononcé. Il peut ainsi à tout moment être expulsé de Suisse. Il s'ensuit que le prononcé d'un travail d'intérêt général n'entre pas en considération, cette sanction apparaissant d'emblée inadaptée (<ref-ruling> consid. 3.3 p. 63 s.).
Quant à l'exécution d'une peine pécuniaire, l'autorité précédente a constaté que le recourant refusait absolument d'admettre l'illicéité de son comportement, qu'il se cachait pour tenter d'échapper à ses conséquences, qu'il continuait à affirmer qu'il ne partirait jamais et qu'au regard de ses antécédents, aucune menace de sanction, ni même l'exécution d'une peine d'emprisonnement n'avaient pu le détourner de son comportement délictueux. Se référant à la jurisprudence du Tribunal fédéral (arrêt 6B_128/2011 du 14 juin 2011), elle a retenu que des motifs de prévention spéciale permettaient de considérer qu'une peine pécuniaire était inexécutable, en particulier lorsque l'intéressé avait démontré l'inutilité de telle peine et/ou une volonté de ne pas tenir compte des sanctions prononcées contre lui, et que tel était le cas en l'espèce. Ce raisonnement ne prête pas le flanc à la critique et la cour cantonale pouvait exclure le prononcé d'une peine pécuniaire, en se fondant sur des motifs de prévention spéciale.
3.4 Au vu de ce qui précède, la cour cantonale peut, sans violation du droit fédéral et à condition que les circonstances personnelles du recourant n'aient pas subi de changement majeur dans l'intervalle, prononcer une courte peine privative de liberté ferme à l'encontre du recourant. Le grief est infondé.
4. Le recourant obtient partiellement gain de cause. Il peut prétendre à une indemnité de dépens réduite (<ref-law>). La demande d'assistance judiciaire est sans objet dans cette mesure. Pour le surplus, bien que rejeté, le recours n'était pas dénué de chances de succès et la situation économique du recourant justifie l'octroi de l'assistance judiciaire (<ref-law>). La complexité de la cause et les intérêts en jeu permettent qu'un avocat d'office lui soit désigné et indemnisé par la caisse du tribunal (<ref-law>). Il n'y a pas lieu de prélever des frais (art. 66 al. 1 et 4 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est partiellement admis, le jugement attaqué est annulé et la cause renvoyée à la cour cantonale afin qu'elle rende une nouvelle décision. Pour le surplus, le recours est rejeté dans la mesure où il est recevable.
2. Il n'est pas perçu de frais judiciaires.
3. L'Etat de Vaud versera au conseil du recourant la somme de 1000 fr. à titre de dépens.
4. La demande d'assistance judiciaire du recourant est admise dans la mesure où elle n'est pas sans objet et Me Charlotte Iselin, avocate à Lausanne lui est désignée comme conseil d'office.
5. La caisse du Tribunal fédéral versera une indemnité de 2000 fr. à Me Charlotte Iselin, au titre de l'assistance judiciaire.
6. Le présent arrêt est communiqué aux parties et à la Cour d'appel pénale du Tribunal cantonal du canton de Vaud.
Lausanne, le 24 janvier 2013
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: Mathys
La Greffière: Livet