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.