Faits: A. Par jugement du 21 juin 2012, le Tribunal de police de l'arrondissement de Lausanne a condamné X._ à une peine pécuniaire de dix jours-amende à 30 francs le jour, avec sursis pendant deux ans, pour avoir séjourné irrégulièrement en Suisse du 1er au 19 décembre 2010 (art. 115 al. 1 let. b de la loi fédérale du 16 décembre 2005 sur les étrangers (ci-après: LEtr; RS 142.20) ). Il a renoncé à révoquer les sursis octroyés les 29 octobre 2009 et 14 septembre 2010 par le Juge d'instruction genevois. B. Par jugement du 12 décembre 2012, la Cour d'appel pénale du Tribunal cantonal vaudois a admis l'appel formé par le Ministère public vaudois et réformé le jugement de première instance en ce sens qu'elle a condamné X._ à une peine pécuniaire de 50 jours-amende à 30 francs le jour, avec sursis pendant quatre ans, ainsi qu'à une amende de 600 francs à titre de sanction immédiate pour avoir séjourné illégalement en Suisse du 13 septembre 2010 au 22 juin 2011. En substance, elle a retenu les faits suivants: X._ est né le 2 février 1987 au Maroc, pays dont il est ressortissant. A une date indéterminée, il s'est établi en Italie au bénéfice d'un permis de séjour et y a travaillé notamment dans le domaine de l'import-export jusqu'en 2010. Dans le courant de l'année 2008, X._ a fait la connaissance de Y._, ressortissante suisse. Le couple a vécu entre la Suisse et l'Italie durant de nombreux mois, l'un rendant visite à l'autre régulièrement pour des week-ends prolongés. Au mois de septembre 2010, X._ a rendu visite à Y._, comme il le faisait régulièrement. Il est entré en Suisse au bénéfice de son autorisation de séjour en Italie, qui l'autorisait à quitter le territoire italien pour se rendre dans les pays de l'espace Schengen. Alors qu'il était en Suisse, il s'est vu notifier le 13 septembre 2010 une interdiction d'entrée sur le territoire suisse liée à de précédentes condamnations prononcées par le Juge d'instruction de Genève. Il a dès lors pris la décision de ne pas retourner en Italie. Il a interjeté des recours contre la décision d'interdiction d'entrée en Suisse. Parallèlement, il a entrepris les démarches pour obtenir l'autorisation de se marier. Le mariage a été célébré le 12 décembre 2011. X._ a obtenu un permis B valable pour les cantons de Vaud et de Lucerne en date du 25 janvier 2012 pour le premier et du 13 février 2012 pour le second. L'Office fédéral des migrations a annulé la décision d'interdiction d'entrée en Suisse le 20 janvier 2012. C. Contre ce dernier jugement, X._ dépose un recours en matière pénale devant le Tribunal fédéral. Il conclut, principalement, à une exemption de toute peine en application de l'art. 52 CP et, subsidiairement, à l'annulation de l'arrêt attaqué et au renvoi de la cause au tribunal de première instance ou à la cour cantonale pour nouveau jugement. Invités à se déterminer, la cour cantonale a renoncé à formuler des observations et le Ministère public a conclu au rejet du recours. Le recourant a répondu aux déterminations du Ministère public. 