Faits :
A.
Par jugement du 26 septembre 2018, le Tribunal de police de l'arrondissement de la Broye et du Nord vaudois a constaté que X._ s'était rendu coupable de séjour illégal et activité lucrative sans autorisation, l'a condamné à une peine privative de liberté de 90 jours, peine partiellement complémentaire à celle prononcée le 21 septembre 2017 par le Ministère public de l'arrondissement de Lausanne, et a renoncé à révoquer le sursis accordé à X._ le 15 février 2016 par le Ministère public de l'arrondissement du Nord vaudois.
B.
Par jugement du 4 janvier 2019, la Cour d'appel pénale du Tribunal cantonal vaudois a rejeté l'appel formé par X._ contre la décision de première instance. Ce jugement se fonde en substance sur les faits suivants.
B.a. Le 9 novembre 2017, X._ a fait l'objet d'un contrôle de gendarmerie à Payerne, alors qu'il circulait au volant d'un véhicule de travail Citroën Berlingo. Il s'est légitimé au moyen d'une carte d'identité du Kosovo et les gendarmes ont dès lors procédé à un examen de sa situation d'étranger. X._ leur a notamment indiqué qu'il faisait des allers-retours entre l'Italie et la Suisse afin de travailler depuis 2013, qu'il était en couple avec Y._, ressortissante suisse, depuis quelques années, qu'il réalisait un revenu d'environ 1'500 fr. par mois en oeuvrant épisodiquement en tant que peintre sur des chantiers à un tarif-horaire de 25 fr. et qu'il ne versait aucune charge sociale ni cotisation d'assurance.
Devant le ministère public, X._ a contesté ses déclarations telles qu'elles figuraient dans le rapport de la gendarmerie du 9 novembre 2017, expliquant qu'il n'était alors pas accompagné d'un interprète et qu'il n'avait par conséquent pas compris ce qu'il avait signé. Il a admis qu'il n'avait pas d'autorisation de travail mais précisé qu'il n'avait jamais perçu de salaire régulier et qu'il contestait avoir jamais réalisé un revenu mensuel de 1'500 francs. Il a indiqué qu'il avait travaillé pour des paysans pour des montants de l'ordre de 200 fr. à 300 fr., uniquement afin de les aider, avant de se rétracter et de déclarer qu'il n'avait en réalité travaillé que pour le beau-frère de Y._. Il a produit copie d'un permis de séjour italien, intitulé Permesso di soggiorno, soggiornante di lungo periodo-CE, qui lui a été délivré le 18 mai 2011 et est valable pour une durée illimitée. Il a également produit son passeport kosovar. Pour la période du 19 avril au 9 novembre 2017 visée par l'accusation, ce document comporte un tampon, du 27 juillet 2017.
B.b. Le casier judiciaire suisse de X._ fait état de trois condamnations, la première, le 1 er avril 2015, à une peine pécuniaire de 40 jours-amende à 50 fr., avec sursis pendant deux ans et amende de 1000 fr. pour activité lucrative sans autorisation (sursis révoqué le 21 septembre 2017), la seconde, le 15 février 2016, à une peine pécuniaire de 60 jours-amende à 30 fr., avec sursis pendant deux ans et amende de 450 fr. (délai d'épreuve prolongé d'un an le 21 septembre 2017) pour violation grave des règles de la circulation routière, et la troisième, le 21 septembre 2017, à une peine privative de liberté de 120 jours pour séjour illégal et activité lucrative sans autorisation.
C.
X._ forme un recours en matière pénale au Tribunal fédéral. Il conclut, avec suite de frais et dépens, principalement à la réforme du jugement entrepris en ce sens qu'il est libéré du chef d'accusation de séjour illégal et condamné à une peine pécuniaire de 30 jours-amende à 30 fr. le jour avec sursis pendant deux ans, subsidiairement qu'il est condamné à une peine pécuniaire de 45 jours-amende à 30 fr. le jour avec sursis pendant deux ans, encore plus subsidiairement qu'il est condamné à une peine privative de liberté de 90 jours avec sursis pendant deux ans. Il sollicite également une indemnité pour les dépenses occasionnées par l'exercice raisonnable de ses droits de procédure.

Considérant en droit :
1.
Le recourant conteste s'être rendu coupable de l'infraction de séjour illégal. Il se plaint d'une constatation arbitraire des faits et de la violation du principe " in dubio pro reo ".
1.1.
1.1.1. Le Tribunal fédéral n'est pas une autorité d'appel, auprès de laquelle les faits pourraient être rediscutés librement. Il est lié par les constatations de fait de la décision entreprise (<ref-law>), à moins qu'elles n'aient été établies 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. Une décision n'est pas arbitraire du seul fait qu'elle apparaît discutable ou même critiquable; il faut qu'elle soit manifestement insoutenable et cela non seulement dans sa motivation mais aussi dans son résultat (<ref-ruling> consid. 2.3.1 p. 244). Le Tribunal fédéral n'entre pas en matière sur les critiques de nature appellatoire (<ref-ruling> consid. 2.4 p. 368 et les références citées).
La présomption d'innocence, garantie par les <ref-law>, 32 al. 1 Cst., 14 par. 2 Pacte ONU II et 6 par. 2 CEDH, ainsi que son corollaire, le principe "in dubio pro reo", concernent tant le fardeau de la preuve que l'appréciation des preuves au sens large (<ref-ruling> consid. 2.2.3.1 p. 348 s.; <ref-ruling> consid. 2a p. 40 s.). Lorsque l'appréciation des preuves et la constatation des faits sont critiquées en référence au principe "in dubio pro reo", celui-ci n'a pas de portée plus large que l'interdiction de l'arbitraire (<ref-ruling> consid. 2.2.3.3 p. 351 s.; <ref-ruling> consid. 1.1 p. 503).
1.1.2. Aux termes de l'art. 115 al. 1 let. b de la Loi fédérale sur les étrangers et l'intégration du 16 décembre 2005 (RS 142.20; LEI), est puni d'une peine privative de liberté d'un an au plus ou d'une peine pécuniaire quiconque séjourne illégalement en Suisse, notamment après l'expiration de la durée du séjour non soumis à autorisation ou du séjour autorisé.
L'étranger qui n'exerce pas d'activité lucrative peut séjourner en Suisse sans autorisation pendant trois mois (art. 10 al. 1 LEI), alors qu'il doit solliciter une autorisation en cas d'activité lucrative, quelle que soit la durée de son séjour (art. 11 al. 1 LEI).
1.2. La cour cantonale a constaté que le recourant ne contestait plus, depuis l'audience d'appel, sa condamnation pour avoir travaillé au noir en Suisse (activité lucrative sans autorisation), au cours de la période du 19 avril au 9 novembre 2017, et qu'il avait reconnu qu'il n'était alors titulaire d'aucune autorisation de travail.
C'est de manière appellatoire, partant irrecevable, que le recourant affirme n'avoir travaillé que " de manière sporadique " en Suisse, sans que l'on ne sache d'ailleurs ce qu'il voudrait en déduire. Pour le surplus, qu'il ait été amené à travailler en Suisse car il vivait avec sa compagne dans ce pays et voulait l'aider financièrement ne change rien au fait qu'il tombait sous le coup de l'art. 11 al. 1 LEI (séjour avec activité lucrative) et non de l'art. 10 al. 1 LEI (séjour de moins de trois mois sans activité lucrative). Il était ainsi soumis à l'obligation de solliciter une autorisation de séjour, quelle que soit la durée de celui-ci, ce qu'il a manqué de faire. Pour ce motif déjà, la cour cantonale pouvait, sans violer le droit fédéral, reconnaître le recourant coupable de séjour illégal.
1.3. A titre subsidiaire, la cour cantonale a considéré que, même si le séjour du recourant en Suisse n'avait pas pour motif l'exercice d'une activité lucrative, il devrait être considéré comme illégal car d'une durée supérieure à trois mois, cela nonobstant son permis de séjour italien. En effet, la période incriminée comportait 204 jours, soit plus de six mois et demi. Or le passeport kosovar du recourant ne comportait qu'un seul tampon daté de cette période, du 27 juillet 2017, et cette date se situait au-delà d'un séjour de trois mois à compter du 19 avril 2017. Ses déclarations, selon lesquelles il aurait effectué des allers-retours à l'étranger, interrompant ses séjours en Suisse avant qu'ils n'atteignent trois mois, n'étaient étayées par aucune explication plausible quant aux motifs de ces déplacements et par aucune date précise, si bien qu'elles n'étaient pas crédibles.
Le recourant soutient qu'il ne saurait lui être reproché de ne pas avoir documenté ses différents allers-retours entre la Suisse et l'Italie, étant notoire qu'il est possible de quitter le territoire suisse ou d'y entrer sans faire l'objet d'aucun contrôle d'identité.
Cet argument est sans fondement. Le recourant pouvait étayer ses allégations de différentes manières, notamment en fournissant des précisions sur ses prétendus voyages en Italie (dates, lieux, raisons du voyage) et tout document susceptible d'en établir l'existence (titres de transport, documents de séjour, justificatifs de retraits d'argent ou de dépenses). Il ne pouvait, en tous les cas, se contenter d'affirmer péremptoirement qu'il avait quitté la Suisse à plusieurs reprises pendant la période visée. C'est sans arbitraire que la cour cantonale a jugé que ses déclarations n'étaient pas crédibles.
Pour ce second motif également, la condamnation du recourant ne viole pas l'art. 115 al. 1 let. b LEI.
2.
Invoquant la violation de l'<ref-law>, le recourant critique la peine privative de liberté ferme (de 90 jours) qui lui a été infligée.
2. Aux termes de l'<ref-law> en vigueur jusqu'au 31 décembre 2017, 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. Cette disposition est applicable en l'espèce sans égard à la modification entrée en vigueur le 1 er janvier 2018, qui n'est pas plus favorable à l'intéressé (cf. <ref-law>; arrêts 6B_279/2019 du 14 mai 2019 consid. 2.1; 6B_887/2017 du 8 mars 2018 consid. 4.1).
Dans la conception de la partie générale du code pénal en vigueur jusqu'à la fin de l'année 2017, la peine pécuniaire constitue la peine 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. En vertu du principe de la proportionnalité, il y a lieu, en règle générale, 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 du condamné, respectivement qui le touche le moins durement. L'intention essentielle au coeur de la révision de la partie générale du code pénal en matière de sanction était 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 envisagée, ses effets sur l'auteur et son milieu social, ainsi que son efficacité préventive (<ref-ruling> consid. 4 p. 100 ss). Lorsque des motifs de prévention spéciale permettent de considérer qu'une peine pécuniaire ou une peine de travail d'intérêt général seraient d'emblée inadaptées, l'autorité peut prononcer une peine privative de liberté de courte durée (arrêts 6B_279/2019 précité consid. 2.2; 6B_887/2017 précité consid. 4.2).
Le juge doit motiver le choix de la courte peine privative de liberté ferme de manière circonstanciée (<ref-law>), mentionnant clairement en quoi il y a lieu d'admettre que la peine pécuniaire ne paraît pas adéquate (<ref-ruling> consid. 8.4 p. 80; arrêt 6B_279/2019 précité consid. 2.2).
2.4. Eu égard à la durée du séjour illégal et du travail au noir, aux trois condamnations pénales antérieures de l'intéressé, dont deux avaient déjà sanctionné des infractions à la législation sur les étrangers, et au comportement du recourant en procédure, caractérisé par le recours au mensonge pour tenter d'échapper aux conséquences de ses actes, la cour cantonale a considéré, à l'instar du ministère public et du premier juge, que la culpabilité du recourant était importante et qu'elle n'était que très modérément réduite par les facteurs à prendre en compte à décharge, soit en particulier sa solvabilité et la régulation de ses conditions de séjour par un mariage. Elle a relevé que le recourant ne faisait certes l'objet d'aucune poursuite ni acte de défaut de biens mais que, sans activité lucrative depuis l'obtention de son permis de séjour en novembre 2018, il était entièrement entretenu financièrement par son épouse. En outre, si une récidive n'était pas envisageable sous l'angle de la LEI, la situation de séjour du recourant en Suisse étant désormais régularisée, le risque de réitération devait être retenu de manière plus globale, le recourant ayant déjà été condamné pour une violation grave des règles de la circulation routière et ayant démontré qu'il était hermétique aux sanctions infligées et dénué de toute prise de conscience. Dans ces circonstances, seul un pronostic défavorable pouvait être posé. Les motifs de prévention spéciale exigeaient qu'une peine privative de liberté et non une peine pécuniaire soit infligée, les jours-amende déjà prononcés à deux reprises ayant démontré leur absence d'impact sur l'intéressé. Une peine privative de liberté de 90 jours était en conséquence adéquate.
2.5. En ce qui concerne les conditions du sursis, le recourant souligne qu'à la suite de son mariage en juin 2018, il est détenteur d'un permis de séjour depuis le 12 novembre 2018, de sorte que le risque de récidive est nul. Il fait valoir qu'il n'a jamais fait l'objet d'aucune poursuite ou acte de défaut de biens, ne s'en est jamais pris à des biens juridiquement protégés tels que le patrimoine ou l'intégrité personnelle et ne représente aucunement une menace pour l'ordre public.
2.2.1. L'examen des conditions de l'octroi ou non du sursis, première condition posée par l'<ref-law>, se fait 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 juge doit formuler un pronostic sur l'amendement de l'auteur. Le défaut de prise de conscience de la faute peut justifier un pronostic défavorable, car seul celui qui se repent de son acte mérite la confiance que l'on doit pouvoir accorder au condamné bénéficiant du sursis (<ref-ruling>; arrêt 6B_1030/2018 du 20 novembre 2018 consid. 4.3). Le juge dispose d'un large pouvoir d'appréciation dans l'émission du pronostic. Le Tribunal fédéral n'intervient que s'il en a abusé, notamment lorsqu'il a omis de tenir compte de critères pertinents et s'est fondé exclusivement sur les antécédents du condamné (<ref-ruling> consid. 4.2 p. 143; <ref-ruling> consid. 2.3 p. 204).
2.2.2. En elle-même, la nature de l'infraction ne fournit aucune indication sur les perspectives d'amendement du condamné (<ref-ruling> consid. 1 p. 258; <ref-ruling> consid. 2 p. 123; arrêt 6B_435/2007 du 12 février 2008 consid. 3.6.1). Comme l'a observé la cour cantonale, si une récidive n'est pas envisageable sous l'angle de la LEI compte tenu du nouveau titre de séjour du recourant, il convient de tenir compte du risque de réitération de manière plus globale, ce d'autant que le recourant a un antécédent qui ne relève pas de la LEI. Dans ce contexte, il était pertinent de prendre en considération, d'une part, le défaut de prise de conscience du recourant et, d'autre part, le fait que les sanctions précédemment infligées, notamment la révocation du sursis accordé le 1 er avril 2015, ne l'ont pas détourné de la commission de nouvelles infractions. Il n'est pas déterminant, dans ce cadre, que le recourant doive encore exécuter la peine privative de liberté de 120 jours à laquelle il a été condamné le 21 septembre 2017, étant précisé que cette condamnation est intervenue pendant la période pénale des infractions jugées dans la présente procédure; ce prononcé n'a, de toute évidence, eu aucun effet sur l'intéressé, qui a persisté dans son comportement contraire au droit.
Au vu de ce qui précède, la cour cantonale n'a pas abusé de son large pouvoir d'appréciation en considérant que le pronostic était défavorable et, partant, le sursis exclu.
2.6. S'agissant de la possibilité d'exécuter une peine pécuniaire, la cour cantonale a considéré, au vu des circonstances du cas d'espèce (cf. consid. 2.2 supra), que la courte peine privative de liberté s'imposait pour des motifs de prévention spéciale, dès lors que les jours-amende déjà prononcés à deux reprises n'avaient pas eu d'impact sur l'intéressé. En outre, si le recourant n'a certes jamais fait l'objet de poursuites, la cour cantonale a relevé qu'il était sans activité lucrative depuis l'obtention de son permis de séjour et était entièrement entretenu financièrement par son épouse.
Dans ces conditions, la cour cantonale pouvait, sans violer le droit fédéral, admettre qu'une nouvelle peine pécuniaire ne produirait pas l'effet escompté et prononcer, pour des motifs de prévention spéciale, une peine privative de liberté de courte durée.
3.
Le recourant s'en prend à la quotité de la peine et invoque la violation de l'<ref-law>. Il soutient que la cour cantonale a fait fi des conséquences de la peine sur son avenir ainsi que de ses motivations. Il n'avait pas contrevenu à la LEI dans le but de s'enrichir, mais avait uniquement travaillé de manière sporadique afin de venir en aide à son épouse ou à ses proches. En outre, une peine complémentaire de cette ampleur, cumulée à celle prononcée le 21 septembre 2017, nuirait sans aucun doute à son intégration en Suisse et ne ferait que prolonger sa situation précaire.
3.1. L'<ref-law> prévoit que le juge fixe la peine d'après la culpabilité de l'auteur. Il prend en considération les antécédents et la situation personnelle de ce dernier ainsi que l'effet de la peine sur son avenir (al. 1). La culpabilité est déterminée par la gravité de la lésion ou de la mise en danger du bien juridique concerné, par le caractère répréhensible de l'acte, par les motivations et les buts de l'auteur et par la mesure dans laquelle celui-ci aurait pu éviter la mise en danger ou la lésion, compte tenu de sa situation personnelle et des circonstances extérieures (al. 2). La culpabilité de l'auteur doit être évaluée en fonction de tous les éléments objectifs pertinents, qui ont trait à l'acte lui-même, à savoir notamment la gravité de la lésion, le caractère répréhensible de l'acte et son mode d'exécution. Du point de vue subjectif, sont pris en compte l'intensité de la volonté délictuelle ainsi que les motivations et les buts de l'auteur. A ces composantes de la culpabilité, il faut ajouter les facteurs liés à l'auteur lui-même, à savoir les antécédents, la réputation, la situation personnelle (état de santé, âge, obligations familiales, situation professionnelle, risque de récidive, etc.), la vulnérabilité face à la peine, de même que le comportement après l'acte et au cours de la procédure pénale (<ref-ruling> consid. 9.1 p. 147; <ref-ruling> consid. 6.1.1 p. 66 s.). Le juge dispose d'un large pouvoir d'appréciation dans le cadre de la fixation de la peine. Le Tribunal fédéral n'intervient que lorsque l'autorité cantonale a fixé une peine en dehors du cadre légal, si elle s'est fondée sur des critères étrangers à l'<ref-law>, si des éléments d'appréciation importants n'ont pas été pris en compte ou, enfin, si la peine prononcée est exagérément sévère ou clémente au point de constituer un abus du pouvoir d'appréciation (<ref-ruling> consid. 5.6 p. 61; arrêt 6B_984/2018 du 4 avril 2019 consid. 3.1).
3.2. Il est inévitable que l'exécution d'une peine ferme d'une certaine durée ait des répercussions sur la vie professionnelle et familiale du condamné. Ces conséquences ne peuvent conduire à une réduction de la peine qu'en cas de circonstances extraordinaires (arrêts 6B_1192/2018 du 23 janvier 2019; 6B_780/2018 du 9 octobre 2018 consid. 2.1; 6B_352/2018 du 27 juillet 2018 consid. 4.1.2). Le recourant ne prétend ni ne démontre que de telles circonstances seraient réalisées en l'espèce. Le fait qu'il déclare vouloir chercher un emploi et s'intégrer en Suisse n'est pas suffisant, dès lors que cette situation ne diffère pas sur ce point de celle de nombreux autres condamnés.
Enfin, le recourant s'écarte de l'établissement des faits du jugement cantonal, sans toutefois en démontrer l'arbitraire, lorsqu'il affirme n'avoir travaillé que pour rendre service à ses proches (consid. 1.1.1 supra).
Compte tenu de ce qui précède, il n'apparaît pas que la peine infligée soit exagérément sévère au point de constituer un abus du pouvoir d'appréciation. Le grief de violation de l'<ref-law> est infondé.
4.
Le recours doit être rejeté. Le recourant, qui succombe, supportera les frais judiciaires (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
Les frais judiciaires, arrêtés à 3'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 12 juin 2019
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
La Greffière : Musy