Faits:
A. Par jugement du 16 novembre 2011, le Tribunal de police de l'arrondissement de Lausanne a condamné X._ pour infraction à la loi fédérale du 26 décembre 2005 sur les étrangers (LEtr; RS 142.20) à soixante jours de privation de liberté.
B. Par jugement du 20 février 2012, la Cour d'appel pénale du Tribunal cantonal vaudois a rejeté l'appel formé par X._ et a confirmé le jugement de première instance. En bref, la condamnation repose sur les faits suivants:
A la suite de faits survenus en 2002, X._ a été condamné le 6 avril 2004 par la Cour de cassation pénale du Tribunal cantonal vaudois pour diverses infractions, parmi lesquelles délit manqué de meurtre, menaces, infractions à la loi fédérale du 20 juin 1997 sur les armes, les accessoires d'armes et les munitions (Loi sur les armes, LArm; RS 514.54) et infraction à l'ancienne loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (LFSEE; abrogée par la LEtr entrée en vigueur le 1er janvier 2008) à neuf ans de réclusion, 300 francs d'amende et à douze ans d'expulsion du territoire suisse. A cette époque, outre l'expulsion judiciaire désormais abolie, il avait été frappé d'une interdiction d'entrée en Suisse pour une durée indéterminée. Après 8 ans de prison, il a été expulsé de Suisse le 5 juillet 2010 et renvoyé par avion à Pristina. X._ est resté au Kosovo durant trois semaines jusqu'au début du mois d'août 2010. Durant cette période, il a refait son passeport et a changé officiellement d'identité, reprenant le nom de son père. En août 2010, il est revenu en Suisse par voiture, via la France, au mépris de l'interdiction d'entrée dont il faisait l'objet. Dès cette période et jusqu'au 22 novembre 2010, date de son interpellation, il a séjourné dans notre pays, d'abord chez un parent, puis chez son amie, qu'il a connue en 2008 lors de sa période de semi-liberté.
C. Contre ce dernier jugement, X._ dépose un recours en matière pénale devant le Tribunal fédéral. Il conclut principalement à sa réforme en ce sens qu'il est condamné à un travail d'intérêt général ou à une peine de jours-amende dont la quotité doit être fixée, la sanction devant être assortie d'un sursis d'une durée de deux ans. Subsidiairement, il conclut au renvoi de la cause.
Il n'a pas été ordonné d'échange d'écritures.

Considérant en droit:
1. Le recourant ne conteste pas le principe de sa condamnation mais le refus du sursis, d'une part, et soutient, d'autre part, que la décision entreprise viole l'<ref-law> en tant qu'elle lui inflige une peine privative de liberté ferme d'une durée inférieure à six mois en lieu et place d'une peine pécuniaire ou d'un travail d'intérêt général.
1.1 Selon 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.
1.2 En l'espèce, il convient préalablement de déterminer si les conditions du sursis sont réunies ou non, point déterminant au regard de l'<ref-law>, étant précisé que cette question se pose dans les mêmes termes, au plan subjectif, quel que soit le type de sanction. Le sursis s'examine ainsi selon les critères posés par l'<ref-law>, qui ont été rappelés dans l'arrêt publié aux <ref-ruling> consid. 2.1; il y est renvoyé. Il est acquis que le recourant remplit les conditions objectives à l'octroi du sursis. Seule se pose la question de savoir si un pronostic défavorable peut être posé.
1.2.1 La cour cantonale a retenu qu'à l'issue de l'exécution de la très lourde peine à laquelle il avait été condamné, le recourant était brièvement retourné dans son pays pour obtenir de nouveaux papiers d'identité et, malgré l'interdiction d'entrer et de séjourner en Suisse, il y était revenu de façon clandestine. Une telle façon d'agir dénotait un mépris singulier pour les lois et une totale insensibilité à la sanction pénale si l'on rapprochait cette nouvelle infraction de la condamnation précédente. La cour cantonale a considéré que seul un pronostic défavorable pouvait être posé et que, par conséquent, un sursis était exclu.
1.2.2 Le recourant se plaint d'une constatation incomplète, partant arbitraire, des faits au motif que la cour cantonale a ignoré les éléments relatifs à sa situation personnelle, professionnelle, familiale, ou encore son comportement dans le cadre de la présente procédure.
Dans le recours en matière pénale, les constatations de fait de la décision entreprise lient le Tribunal fédéral (<ref-law>). Il n'en va différemment que si le fait a été établi en violation du droit ou de manière manifestement inexacte au sens des art. 97 al. 1 et 105 al. 2 LTF, soit pour l'essentiel de façon arbitraire au sens de l'art. 9 Cst. (cf. <ref-ruling> consid. 4.1.2 p. 62; sur la notion d'arbitraire, voir <ref-ruling> consid. 7.1 p. 51; <ref-ruling> consid. 7 p. 82). Ce moyen d'ordre constitutionnel (<ref-law>) suppose une argumentation claire et détaillée (<ref-ruling> consid. 1.4 p. 287), circonstanciée (<ref-ruling> consid. 3, p. 105). Les critiques de nature appellatoire sont irrecevables (<ref-ruling> c. 5.1 p. 356 et les références citées).
La cour cantonale a relevé que le recourant bénéficiait d'un emploi au Kosovo, qu'il avait le projet d'épouser son amie, domiciliée en Suisse, tout en rappelant que les démarches administratives nécessaires à ce mariage en étaient au stade d'un recours à la Cour de droit administratif et public au Tribunal cantonal (CDAP) à l'encontre du refus du Service de la population d'autoriser l'entrée ou le séjour du recourant en Suisse. Elle a par ailleurs relevé qu'il avait requis un sauf-conduit pour se présenter à l'audience d'appel. En outre, lorsqu'il affirme qu'il n'a jamais caché aux autorités suisses sa présence sur le territoire helvétique, il s'écarte des faits retenus de nature à lier le Tribunal fédéral (<ref-law>), selon lesquels il est entré clandestinement en Suisse sous une nouvelle identité. Le fait qu'il ait déposé des papiers en vue de se marier n'est pas de nature à remettre en cause cette appréciation, ce d'autant qu'il agissait sous une nouvelle identité. Le grief relatif à la constatation incomplète, respectivement arbitraire, des faits doit être ainsi rejeté.
1.2.3 Le recourant affirme que la cour cantonale a fondé le pronostic défavorable sur la seule base de sa précédente condamnation en 2004.
Cette critique est infondée. La cour cantonale s'est livrée à une appréciation de l'ensemble des circonstances qui ont entouré le retour du recourant en Suisse au mépris de l'interdiction d'entrée dont il faisait l'objet. Elle a ainsi pris en considération la longue peine qu'il avait purgée, près de huit ans, le bref laps de temps durant lequel il était resté au Kosovo après son renvoi de Suisse, le fait qu'il avait mis à profit ce temps pour obtenir une nouvelle identité ainsi que son retour clandestin en Suisse.
1.2.4 Le recourant expose encore que la cour cantonale n'a pas pris en considération dans l'appréciation du pronostic sa situation personnelle au moment du jugement, ni l'état d'esprit qu'il avait manifesté en retournant dans son pays d'origine pour y travailler ainsi que sa prise de conscience et son amendement qui se sont manifestés par son respect pour l'ordre juridique suisse en répondant aux convocations de la police et en se présentant devant les juridictions de jugement au bénéfice d'un sauf-conduit.
Pour émettre le pronostic, le juge doit se livrer à une appréciation d'ensemble, tenant compte des circonstances de l'infraction, des antécédents de l'auteur, de sa réputation et de sa situation personnelle au moment du jugement, notamment de l'état d'esprit qu'il manifeste. Il doit tenir compte de tous les éléments propres à éclairer l'ensemble du caractère de l'accusé et ses chances d'amendement. Il ne peut accorder un poids particulier à certains critères et en négliger d'autres qui sont pertinents (<ref-ruling> consid. 4.2.1 p. 5). Dans l'émission du pronostic, le juge dispose d'un large pouvoir d'appréciation, de sorte que le Tribunal fédéral n'intervient qu'en cas d'excès ou d'abus de celui-ci (<ref-ruling> consid. 3a p. 198; <ref-ruling> consid. 3b p. 198; arrêt 6B_494/2011 du 4 octobre 2011 consid. 3.2).
Comme relevé supra (consid.1.2.2), les circonstances invoquées par le recourant n'ont pas été ignorées par la cour cantonale. Toutefois, celle-ci a manifestement considéré qu'en dépit de ces éléments, le pronostic était défavorable, la façon d'agir du recourant dénotant un mépris singulier pour les lois et une totale insensibilité à la sanction pénale. Compte tenu de la proximité dans le temps entre sa sortie de prison et son retour en Suisse sous une nouvelle identité, de ses lourds antécédents, et des conditions de son retour en Suisse, la cour cantonale pouvait inférer de ces circonstances qu'il était insensible à la sanction pénale. La nouvelle stabilité professionnelle du recourant et son bon comportement depuis son interpellation dans le cadre de la présente procédure ne sauraient suffire à renverser ce pronostic, en particulier en raison du caractère très récent de ces facteurs qui ne permet pas d'apprécier la réalité et la mesure de l'amendement du recourant. Au surplus, il n'y a rien d'exceptionnel à ce qu'il se soit présenté aux audiences de jugement de première instance et d'appel dès lors que l'on peut attendre de tout prévenu qu'il donne suite aux convocations.
1.2.5 En définitive, les éléments invoqués par l'autorité cantonale lui permettaient donc, sans abus du pouvoir d'appréciation, de poser un pronostic défavorable sur le comportement à venir du recourant et de lui refuser le sursis.
1.3 Dès lors que le pronostic est défavorable et que, par conséquent, un sursis est exclu, la première condition de l'<ref-law> est réalisée. Il convient ensuite d'examiner la seconde condition de la disposition précitée, à savoir de déterminer si une peine pécuniaire, respectivement un travail d'intérêt général, peuvent être exécutés.
A titre de sanctions, le nouveau droit 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 nouvelle 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; arrêt 6B_128/2011 du 14 juin 2011 consid. 3.1).
1.3.1 La cour cantonale a motivé le refus de la peine pécuniaire par des considérations de prévention spéciale en relevant qu'après huit ans de réclusion, le recourant n'avait pas hésité à récidiver en commettant une infraction crasse à la LEtr, ce qui dénotait un individu se croyant au-dessus des lois et insensible aux sanctions pénales les plus lourdes.
Certes, comme le relève le recourant, les faits qui ont fondé sa condamnation antérieure remontent à plus de dix ans, toutefois cette circonstance n'est pas déterminante sur l'efficacité préventive du choix de la peine à prononcer à son encontre dans le cas d'espèce. Il est constant que le recourant a commis la nouvelle infraction dans les semaines qui ont suivi sa libération. Or, c'est cette proximité temporelle qui permet de retenir que la cour cantonale pouvait sans violer le droit fédéral considérer que, là où l'effet dissuasif d'une longue peine de privation de liberté avait échoué, une peine pécuniaire ferme n'entrait pas en considération, le comportement du recourant attestant un total mépris des règles en vigueur.
1.3.2 Selon la jurisprudence, le prononcé d'un travail d'intérêt général n'est justifié qu'autant que l'on puisse au moins prévoir que l'intéressé pourra, cas échéant après l'exécution, poursuivre son évolution en Suisse. Lorsqu'il est d'avance exclu que l'étranger demeure en Suisse, ce but ne peut être atteint. Aussi, lorsqu'il n'existe, au moment du jugement, aucun droit de demeurer en Suisse, ou lorsqu'il est établi qu'une décision définitive a été rendue sur son statut en droit des étrangers et qu'il doit quitter la Suisse, le travail d'intérêt général ne constitue pas une sanction adéquate, il est exclu (arrêt 6B_128/2011 du 14 juin 2011 consid. 3.5.2; 6B_541/2007 du 13 mai 2008 consid. 4.2.4).
En l'espèce, la cour cantonale a exclu le travail d'intérêt général au motif que le recourant faisait l'objet d'une décision d'interdiction d'entrée en Suisse entrée en force. Cette décision ne souffre aucune critique et est conforme à la jurisprudence mentionnée. Le fait qu'aucune nouvelle décision définitive n'ait été rendue par la CDAP au moment du jugement cantonal (consid. 1.2.2) n'est pas de nature à remettre en cause cette appréciation. Au moment du prononcé du jugement cantonal, le recourant ne bénéficiait d'aucun droit de pénétrer et de séjourner en Suisse.
1.4 Il résulte de ce qui précède que la seule perspective de devoir exécuter une peine pécuniaire n'a aucun effet dissuasif sur le recourant et que le travail d'intérêt général est exclu pour des raisons tenant à son statut en Suisse. Dans ces conditions, le cour cantonale n'a pas violé le droit fédéral en prononçant une courte peine privative de liberté à l'encontre du recourant.
1.5 Le recourant, qui succombe, supporte les frais de justice (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, arrêtés à 4'000 fr., sont mis à la charge du recourant.
3. 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 4 octobre 2012
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: Mathys
Le Greffier: Rieben