Faits :
A.
Par jugement du 21 octobre 2015, le Tribunal de police de l'arrondissement de La Côte a constaté que X._ s'était rendu coupable d'infraction à la Loi fédérale sur les étrangers, l'a condamné à une peine privative de liberté ferme de 60 jours, a renoncé à révoquer la libération conditionnelle qui lui avait été octroyée par le Tribunal d'application des peines et mesures de Genève dans sa décision du 24 août 2014, a prononcé un avertissement à son endroit et a mis à sa charge les frais de procédure.
B.
Par jugement du 8 mars 2016, la Cour d'appel pénale du Tribunal cantonal vaudois a rejeté l'appel de X._ contre la décision de première instance.
Ce jugement repose en substance sur les faits suivants.
X._ est ressortissant de Guinée-Bissau. Il a fait l'objet d'une décision de renvoi de Suisse rendue le 5 octobre 2012 par l'Office fédéral des migrations et entrée en force le 8 novembre 2012. X._ a été interpellé à Nyon les 21 janvier et 15 février 2015.
C.
X._ forme un recours en matière pénale auprès du Tribunal fédéral contre le jugement cantonal et conclut, avec suite de frais et dépens, à sa réforme en ce sens qu'il est acquitté du chef d'infraction à l'art. 115 al. 1 let. b LEtr et la cause est renvoyée à la cour cantonale pour nouvelle décision sur les frais et les dépens de la procédure antérieure. Il conclut subsidiairement au renvoi de la cause à la cour cantonale pour nouvelle décision. Il sollicite par ailleurs le bénéfice de l'assistance judiciaire.

Considérant en droit :
1.
Selon le recourant, la cour cantonale serait tombée dans l'arbitraire en retenant qu'il ne s'était pas conformé à sa décision de renvoi de Suisse.
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 ne peut revoir les faits établis par l'autorité précédente que si ceux-ci l'ont été de manière manifestement inexacte (<ref-law>), c'est-à-dire arbitraire (sur cette notion, cf. <ref-ruling> consid. 6.1 p. 205) et pour autant que la correction du vice soit susceptible d'influer sur le sort de la cause (<ref-law>). En bref, 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.
Le grief d'arbitraire doit être invoqué et motivé de manière précise (<ref-law>). Le recourant doit exposer, de manière détaillée et pièces à l'appui, que les faits retenus l'ont été d'une manière absolument inadmissible, et non seulement discutable ou critiquable. Il ne saurait se borner à plaider à nouveau sa cause, contester les faits retenus ou rediscuter la manière dont ils ont été établis comme s'il s'adressait à une juridiction d'appel (<ref-ruling> consid. 3 p. 352; <ref-ruling>). Le Tribunal fédéral n'entre pas en matière sur les critiques de nature appellatoire (<ref-ruling> consid. 1.3.1 p. 253).
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 (<ref-ruling> consid. 2a p. 40 s.). Lorsque, comme en l'espèce, 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. 7 p. 82).
1.2. Il n'est pas contesté que le recourant a fait l'objet d'une décision de l'Office fédéral des migrations du 5 octobre 2012 rejetant sa demande d'asile et lui impartissant un délai au 30 novembre 2012 pour quitter la Suisse. Or, la cour cantonale a constaté, en se fondant sur les informations transmises par le Service de la population du canton de Vaud, que le recourant n'avait pas quitté la Suisse dans le délai imparti. Il ressortait en outre des déclarations du recourant qu'il était demeuré en Suisse - auprès de son amie à A._ - ensuite de sa libération conditionnelle prononcée le 27 août 2014 par le Tribunal d'application des peines et mesures de Genève tout en effectuant des allers-retours jusqu'à ce jour entre le territoire helvétique et divers pays européens. Au regard notamment de la décision de l'Office fédéral des migrations, il y avait lieu de considérer que le recourant n'était pas autorisé à séjourner en Suisse pendant toute cette période.
1.2.1. Le recourant se borne à opposer sa version des faits à celle de la cour cantonale, sans toutefois démontrer en quoi l'établissement des faits du jugement attaqué serait gravement erroné. Il est ainsi douteux que sa motivation remplisse les exigences de l'<ref-law>.
1.2.2. Quoi qu'il en soit, en affirmant qu'il s'est conformé à la décision de renvoi dans la mesure où il s'est rendu au Portugal pour obtenir une carte de résidence permanente et n'est dès lors plus revenu en Suisse que pour des périodes inférieures à 90 jours sur 180 jours, le recourant ne démontre pas l'arbitraire des constatations cantonales. En effet, il n'établit pas, en particulier, avoir formellement quitté la Suisse, l'Office fédéral des migrations ayant constaté à l'inverse que le recourant avait disparu, rendant ainsi vaines les démarches en vue de l'exécution de son renvoi (pièce 12). En outre, selon ses propres dires, s'il s'était rendu au Portugal à un moment donné après le prononcé de son renvoi, il était ensuite revenu en Suisse. Placé en détention en Suisse du 27 octobre 2013 au 27 août 2014, il s'était rendu au Portugal deux mois après sa sortie de prison et était revenu en Suisse deux semaines plus tard. Il résidait actuellement auprès de sa compagne, dont il avait eu un enfant le 15 mai 2015 (jugement de première instance du 21 octobre 2015, p. 3).
Fondée sur les informations transmises par le Service de la population ainsi que sur les déclarations de l'intéressé, la cour cantonale pouvait retenir sans arbitraire que le recourant était demeuré en Suisse en dépit de sa décision de renvoi, ne faisant que de brèves escapades à l'étranger. Le grief d'arbitraire dans l'établissement des faits est dès lors infondé, dans la mesure de sa recevabilité.
2.
Le recourant conteste avoir dépassé la durée de son séjour légal en Suisse et se prévaut de sa carte de résidence permanente délivrée par le Portugal. Or dans la mesure où il est admis (consid. 1 supra) que le recourant était toujours sous le coup de la décision de renvoi, il n'avait pas le droit de séjourner sur le territoire suisse. Par surabondance, et à supposer qu'il eût disposé d'une carte de résidence portugaise valable l'autorisant à effectuer des séjours de courte durée en Suisse sans obligation de visa, il y a lieu de considérer ce qui suit.
2.1. Indépendamment de toute autorisation, les étrangers sans activité lucrative peuvent séjourner en Suisse pendant trois mois (art. 10 LEtr). Si l'étranger doit avoir un visa (art. 5 al. 1 let. a LEtr), c'est la durée fixée dans le visa qui sera déterminante (art. 10 al. 1 in fine LEtr). Comme le précise l'art. 9 de l'ordonnance relative à l'admission, au séjour et à l'exercice d'une activité lucrative (OASA; RS 142.201), le séjour ne doit pas excéder trois mois " sur une période de six mois à partir de l'entrée en Suisse ". Le séjour doit être interrompu après trois mois; selon la pratique des autorités fédérales, une interruption n'est admise que si l'étranger séjourne au moins un mois à l'étranger. Plusieurs séjours sur une période de six mois sont possibles, pour autant que la durée maximale de la présence en Suisse ne dépasse pas trois mois (arrêt 6B_839/2015 du 26 août 2016 consid. 4.1 et la référence citée).
2.2. S'il soutient n'être jamais resté en Suisse plus de trois mois, le recourant ne conteste pas n'avoir fait que de brèves escapades à l'étranger, à l'instar de son séjour au Portugal durant le deuxième semestre 2014, qui n'a duré que deux semaines. Même à admettre que ses déplacements à l'étranger intervenaient au moins tous les trois mois, ils étaient donc trop courts pour interrompre son séjour en Suisse, qui a ainsi duré davantage que trois mois sur une période de six mois, soit au-delà de la durée admissible selon l'art. 9 OASA.
3.
Rappelant l'existence du Protocole additionnel II (RS 0.142.112.681.1) relatif à l'Accord du 21 juin 1999 entre la Confédération suisse, d'une part, et la Communauté européenne et ses Etats membres, d'autres part, sur la libre circulation des personnes (ALCP; RS 0.142.112.681), le recourant relève que les ressortissants d'États de l'Union européenne, en particulier les ressortissants roumains, sont exemptés de l'obligation de visa pour entrer en Suisse et doivent obtenir une autorisation pour séjourner au-delà de trois mois. Il soutient qu'il n'a fait que violer les prescriptions concernant les déclarations d'arrivée ou d'annonce en Suisse.
Dans la mesure où il est établi que le recourant est un ressortissant de Guinée-Bissau, l'argumentation présentée est dénuée de toute pertinence. Quoi qu'il en soit, le recourant ne démontre pas qu'il aurait rempli les conditions d'octroi d'une autorisation de séjour en Suisse.
4.
Compte tenu des considérants qui précèdent, la cour cantonale pouvait retenir que le recourant ne bénéficiait d'aucun droit de séjour en Suisse lorsqu'il a été appréhendé par la police de Nyon les 21 janvier et 15 février 2015, de sorte que l'art. 115 al. 1 let. b LEtr était applicable au cas d'espèce.
5.
Pour le surplus, le recourant ne conteste ni la qualification juridique ni la peine qui lui a été infligée en vertu de l'art. 115 al. 1 let. b LEtr, que ce soit dans sa nature ou sa quotité, pas plus qu'il ne remet en cause, conformément à l'<ref-law>, le raisonnement de la cour cantonale qui exclut l'application de la Directive 2008/115/CE relative aux normes et procédures communes applicables dans les États membres au retour des ressortissants de pays tiers en séjour irrégulier (Directive sur le retour).
Il résulte de ce qui précède que le recours doit être rejeté dans la mesure de sa recevabilité. Les conclusions étant vouées à l'échec, l'assistance judiciaire est refusée au recourant (<ref-law>). Celui-ci supportera les frais judiciaires (<ref-law>), dont le montant sera fixé en tenant compte de sa situation financière (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté dans la mesure où il est recevable.
2.
La demande d'assistance judiciaire est rejetée.
3.
Les frais judiciaires, arrêtés à 1200 fr., sont mis à la charge du recourant.
4.
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 13 juin 2017
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
La Greffière : Musy