Faits :
A.
Par ordonnance pénale du 28 mai 2018, le Ministère public de l'arrondissement de Lausanne a reconnu A._ coupable de séjour illégal et l'a condamné à une peine privative de liberté de 30 jours (AM18.008147-AMLN). Le prénommé avait fait l'objet d'un contrôle de police le 22 avril 2018 à B._, en marge d'une bagarre. Il s'était avéré qu'il se trouvait sous le coup d'une interdiction d'entrée et de séjour en Suisse valable du 14 novembre 2017 au 13 novembre 2027.
La communication de l'ordonnance précitée n'a pas abouti, le pli ayant été retourné au ministère public avec la mention "destinataire introuvable à l'adresse indiquée", soit, à teneur du procès-verbal d'examen de situation de l'intéressé, "xxx C._, rue D._".
Le 14 juin 2018, le ministère public a demandé à la police de procéder à une recherche du lieu de séjour de A._. Les rechercheseffectuées sont demeurées infructueuses.
Le procès-verbal des opérations indique, à la date du 9 juillet 2018, "ordonnance pénale exécutoire (pas d'opposition) ".
B.
Par ordonnance pénale du 10 janvier 2019, le Ministère public de l'arrondissement de Lausanne a reconnu A._ coupable de séjour illégal et l'a condamné à une peine privative de liberté de 30 jours (AM18.022449-AMLN). Cette seconde ordonnance pénale était consécutive à un nouveau contrôle de police dont le prénommé avait fait l'objet le 28 octobre 2018. Il s'était une nouvelle fois avéré que A._ était en situation illégale en Suisse, qu'il avait déjà fait l'objet de sept interpellations depuis 2014 pour des infractions à la LEtr (Loi fédérale du 16 décembre 2015 sur les étrangers; LEI à compter du 1 er janvier 2019; RS 142.20) et qu'il était sous le coup d'une interdiction d'entrée et de séjour valable du 30 mars 2018 au 13 novembre 2027. Le prénommé avait refusé de répondre aux questions de la police.
L'adresse indiquée dans le procès-verbal d'examen de situation signé par A._ était "xxx C._, rue D._, chez sa mère". L'ordonnance précitée y a été adressée par pli recommandé, lequel a été distribué au guichet postal de C._ en date du 16 janvier 2019. Aucune opposition n'a été formée en temps utile et l'ordonnance est ainsi devenue exécutoire à l'issue du délai d'opposition.
C.
En date du 7 février 2019, A._ s'est adressé au ministère public pour faire valoir que les autorités administratives compétentes étaient entrées en matière sur une demande de réexamen, que son renvoi était suspendu, qu'une admission provisoire avait été accordée avec effet au 5 novembre 2018 et qu'un permis F lui avait été délivré. Dans le même courrier, A._ a sollicité la restitution du délai d'opposition à l'ordonnance de condamnation, transmise par lui à son avocat le 6 février 2019, tout en expliquant qu'il n'habitait plus chez sa mère depuis plusieurs mois en raison d'un conflit familial.
Le 22 février 2019, le ministère public a refusé de restituer le délai d'opposition au motif que la notification de l'ordonnance était valable et que le condamné ne pouvait pas se prévaloir d'un empêchement non fautif au sens de l'<ref-law>.
D.
Par actes du 14 juin 2019, A._ a formé deux demandes de révision contre les ordonnances pénales des 28 mai 2018 et 10 janvier 2019 et a conclu à son acquittement. Il a également conclu à la désignation d'un défenseur d'office.
Par jugement du 3 juillet 2019, la Cour d'appel pénale du Tribunal cantonal vaudois a déclaré irrecevables les demandes de révision de A._, mis les frais de la procédure à sa charge et rejeté sa requête tendant à la désignation d'un défenseur d'office.
E.
A._ forme un recours en matière pénale au Tribunal fédéral contre le jugement du 3 juillet 2019 de la Cour d'appel pénale. Il conclut, avec suite de frais et dépens, à la réforme du jugement attaqué, en ce sens qu'il est entré en matière sur ses demandes de révision du 14 juin 2019, que les frais de la procédure de révision sont mis à la charge de l'État et que la requête en désignation d'un défenseur d'office est admise. Subsidiairement, il conclut à l'annulation du jugement attaqué et au renvoi de la cause à l'autorité précédente pour nouvelle décision dans le sens des considérants de l'arrêt à intervenir. Il sollicite également le bénéfice de l'assistance judiciaire.
F.
Invités à se déterminer, la Cour d'appel pénale du Tribunal cantonal vaudois et le ministère public y ont renoncé et se sont référés aux considérants du jugement attaqué.

Considérant en droit :
1.
A l'appui de ses deux demandes de révision, le recourant a fait valoir devant la cour cantonale qu'il avait le droit de séjourner en Suisse lorsqu'il a été interpellé par la police en date des 22 avril 2018 et 28 octobre 2018. Les juges précédents ont relevé qu'il avait produit des pièces à cet égard. Sur la base de ces dernières, le recourant a fait état, devant la cour cantonale, d'une procédure de réexamen. Il a en outre allégué que, dans le cadre de cette procédure, le Tribunal administratif fédéral avait successivement rendu une décision de suspension provisoire de l'exécution de sa procédure de renvoi le 27 novembre 2017, une décision incidente le 19 décembre 2017 - qui confirmait la mesure provisoire du 27 novembre 2017 en précisant que le recourant pouvait attendre en Suisse l'issue de la procédure -, puis un arrêt le 3 octobre 2018, à la suite duquel il a été mis au bénéfice d'une admission provisoire avec effet au 5 novembre 2018.
Devant le Tribunal fédéral, le recourant soutient en outre que la protection provisoire dont il s'est prévalu en instance cantonale ressortait également des rapports de police établis des 22 avril et 28 octobre 2018, qui comportent tous deux la mention, en lien avec la date du 27 novembre 2017, "recours, fin AP/protec. provisoire" (pièce 4, p. 4 [AM18.008147-AMLN]; pièce 4, p. 4 [AM18.022449-AMLN]).
2.
Pour déclarer irrecevables les deux demandes de révision du recourant, la cour cantonale a d'abord relevé que l'ordonnance pénale du 28 mai 2018 avait été, au vu des circonstances - à savoir l'adresse indiquée par le recourant lors de son audition par la police, l'échec de la notification par pli recommandé et les recherches ordonnées par le ministère public et demeurées infructueuses -, notifiée conformément à l'<ref-law>, en vertu de la fiction prévue par cette disposition. Elle était entrée en force, faute d'opposition, tout comme l'ordonnance du 10 janvier 2019, qui avait été notifiée à la même adresse que la précédente, par pli recommandé et retirée au guichet postal le 16 janvier suivant.
La cour cantonale a ensuite considéré que le recourant aurait dû former opposition aux ordonnances des 28 mai 2018 et 10 janvier 2019 et, à l'égard de cette dernière, en faisant valoir que son statut en droit des étrangers avait évolué, que son renvoi avait été suspendu dans le cadre d'une procédure de réexamen et qu'il bénéficiait d'une admission provisoire avec effet au 5 novembre 2018. Bien qu'ayant eu connaissance de ces faits lorsque la deuxième ordonnance avait été rendue et n'ayant aucune raison de taire les moyens qu'il invoquait à l'appui de ses demandes de révision, il n'avait pas manifesté son opposition. Or, selon la cour cantonale, la voie de la révision n'est pas ouverte lorsque le prévenu n'a pas préalablement agi par la voie de l'opposition. Pour les juges précédents, il était ainsi manifeste que le recourant cherchait à remettre en cause des ordonnances entrées en force en éludant les voies de droit idoines et usuelles.
Par surabondance, la cour cantonale a encore relevé que le nouveau statut administratif du recourant avec effet au 5 novembre 2018 ne pouvait constituer un motif de révision pour un séjour illégal antérieur, soit constaté le 22 avril 2018.
3.
Selon l'<ref-law>, toute personne lésée par un jugement ou une ordonnance pénale entrés en force peut en demander la révision s'il existe des faits ou des moyens de preuve qui étaient inconnus de l'autorité inférieure et qui sont de nature à motiver l'acquittement ou une condamnation sensiblement moins sévère ou plus sévère du condamné.
3.1. Les faits ou moyens de preuve sont inconnus lorsque le juge n'en a pas eu connaissance au moment où il s'est prononcé, c'est-à-dire lorsqu'ils ne lui ont pas été soumis sous quelque forme que ce soit (<ref-ruling> consid. 5.1.2 p. 66 s.; <ref-ruling> consid. 1 p. 73; arrêts 6B_1110/2019 du 18 décembre 2019 consid. 1.1.1; 6B_342/2019 du 9 juillet 2019 consid. 1.1).
Ils sont sérieux lorsqu'ils sont propres à ébranler les constatations de fait sur lesquelles se fonde la condamnation et que l'état de fait ainsi modifié rend possible un jugement sensiblement plus favorable au condamné (<ref-ruling> consid. 1.1 p. 199; <ref-ruling> consid. 5.1.4 p. 68; <ref-ruling> consid. 1 p. 73; arrêts 6B_1110/2019 précité consid. 1.1.1; 6B_342/2019 précité consid. 1.1; 6B_574/2019 du 9 septembre 2019 consid. 1.1).
3.2. La procédure du rescindant instituée par le CPP se déroule, en principe, en deux phases, à savoir un examen préalable de la recevabilité (art. 412 al. 1 et 2 CPP) et un examen des motifs invoqués (art. 412 al. 3 et 4 et 413 CPP). Il s'agit de deux étapes d'une seule et même procédure, pour laquelle la juridiction d'appel est compétente (art. 412 al. 1 et 3 CPP).
Selon l'<ref-law>, la juridiction d'appel n'entre pas en matière si la demande de révision est manifestement irrecevable ou non motivée ou si une demande de révision invoquant les mêmes motifs a déjà été rejetée par le passé. Cet examen préalable et sommaire porte principalement sur les conditions formelles de recevabilité de la demande de révision. L'autorité saisie peut toutefois également refuser d'entrer en matière lorsque les motifs de révision invoqués sont manifestement non vraisemblables ou infondés (<ref-ruling> consid. 3.5 p. 129) ou encore lorsque la demande de révision apparaît abusive (arrêts 6B_1110/2019 précité consid. 1.1.2 et les références citées; 6B_1126/2019 du 4 novembre 2019 consid. 1.1; 6B_1170/2015 du 10 octobre 2016 consid. 2).
La révision ne doit pas servir à remettre sans cesse en cause une décision entrée en force, à détourner les dispositions légales sur les délais de recours ou celles sur la restitution des délais, voire à introduire des faits non présentés dans le premier procès en raison d'une négligence procédurale (<ref-ruling> consid. 1.1 p. 199; <ref-ruling> consid. 2.2 p. 74; arrêt 6B_273/2020 du 27 avril 2020 consid. 1.2 et les références citées).
3.3. Les conditions d'une révision visant une ordonnance pénale sont restrictives. L'ordonnance pénale est rendue dans le cadre d'une procédure spéciale. Elle a pour spécificité de contraindre le condamné à prendre position. Une absence de réaction de sa part s'interprète comme un acquiescement. Il doit s'opposer dans le délai prévu à cet effet s'il n'adhère pas à sa condamnation, par exemple parce qu'il entend se prévaloir de faits omis qu'il considère comme importants. Le système serait compromis si, une fois le délai d'opposition échu sans avoir été utilisé, le condamné pouvait revenir sur l'acquiescement ainsi donné et demander selon son bon vouloir la révision de l'ordonnance pénale pour des faits qu'il aurait déjà pu faire valoir dans une procédure ordinaire en manifestant son opposition (ATF <ref-ruling> consid. 2.3 p. 75 s.; arrêt 6B_662/2019 du 23 août 2019 consid. 1.1). Il s'ensuit qu'une demande de révision dirigée contre une ordonnance pénale doit être qualifiée d'abusive si elle repose sur des faits que le condamné connaissait initialement, qu'il n'avait aucune raison légitime de taire et qu'il aurait pu révéler dans une procédure ordinaire mise en oeuvre par une simple opposition. En revanche, une révision peut entrer en considération à l'égard d'une ordonnance pénale pour des faits et des moyens de preuve importants que le condamné ne connaissait pas au moment du prononcé de l'ordonnance ou dont il ne pouvait pas se prévaloir ou n'avait pas de raisons de se prévaloir à cette époque (<ref-ruling> consid. 1.1 p. 199; <ref-ruling> consid. 2.3 p. 75 s.; arrêt 6B_662/2019 précité consid. 1.1).
L'abus de droit ne sera cependant admis qu'avec retenue. Il s'agit, dans chaque cas d'examiner, au regard des circonstances de l'espèce, si la demande tend à contourner les voies de droit ordinaires (<ref-ruling> consid. 1.1 p. 199; <ref-ruling> consid. 2.2 p. 74 et consid. 2.4 p. 76; arrêt 6B_273/2020 précité consid. 1.2 et les références citées).
4.
Invoquant une violation de l'<ref-law> et une constatation arbitraire des faits, le recourant reproche en substance à la cour cantonale de lui avoir imputé à tort un procédé abusif en retenant que ses demandes de révision visaient à contourner les voies de droit ordinaires. Ce faisant, le recourant lui reproche d'avoir rendu une décision d'irrecevabilité en application de l'<ref-law> sans que les conditions en soient remplies.
4.1. S'agissant de l'ordonnance pénale du 28 mai 2018, la prémisse de la motivation cantonale repose sur l'application de l'<ref-law>, partant sur la fiction de notification prévue par cette disposition. Le recourant ne discute pas en soi les conditions d'application de l'<ref-law>. Il n'y a dès lors pas lieu de s'y arrêter plus avant. Le recourant conteste cependant que l'on puisse lui opposer cette fiction de notification pour ensuite lui reprocher de ne pas avoir formé opposition en temps utile et retenir, faute d'opposition, un procédé abusif au point de déclarer ses demandes de révision irrecevables.
Il convient à cet égard de relever que le Tribunal fédéral a eu l'occasion de souligner à plusieurs reprises le caractère potentiellement problématique de cette disposition au regard des garanties déduites des art. 29 Cst., 29a Cst. et 6 ch. 1 CEDH (arrêts 6B_70/2018 du 6 décembre 2018 consid. 1.2; 6B_141/2017 du 22 décembre 2017 consid. 2.1 et les références citées; 6B_738/2011 du 20 mars 2012 consid. 3.1; cf. sur la problématique connexe liée à la fiction prévue par les <ref-law> et 356 al. 4 CPP: <ref-ruling> consid. 1 p. 32 ss; <ref-ruling> consid. 3.1 p. 159 s. et 3.4 p. 161 s.; <ref-ruling> consid. 2.3 p. 84 et 2.6 p. 86; arrêt 6B_1298/2018 du 21 mars 2019 consid. 3.1 et les références citées, non publié aux <ref-ruling>). Cela étant, l'application de l'<ref-law> s'inscrit en l'espèce dans une procédure où, à teneur du jugement querellé, le recourant a été entendu à une seule reprise en qualité de prévenu par la police, dans la foulée du contrôle dont il a fait l'objet en date du 22 avril 2018. Le procès-verbal des opérations, auquel la cour cantonale se réfère au sujet de la mention relative au caractère exécutoire de l'ordonnance pénale du 28 mai 2018, n'évoque aucune audition ultérieure du recourant par le ministère public. Il apparaît au contraire que l'ordonnance en cause a été immédiatement rendue, sans ouverture formelle d'instruction (cf. <ref-law> cum <ref-law>). En tout état, le recourant n'a pas eu concrètement connaissance de l'ordonnance pénale en cause, alors qu'au préalable, il n'a jamais eu l'occasion de faire valoir ses droits au cours d'une instruction (<ref-law>).
De ce point de vue, le raisonnement suivi par la cour cantonale pour qualifier d'abusive la démarche du recourant demeure essentiellement axé sur les manquements qui lui sont imputables en termes de devoirs procéduraux (cf. sur ce point: arrêt 6B_401/2019 du 1er juillet 2019 consid. 2.5 et les références citées) et ne saurait être partagé, compte tenu des spécificités procédurales du cas d'espèce. L'application conjuguée de l'<ref-law> et de l'<ref-law> génère une situation dans laquelle le recourant se trouve, comme il le relève à juste titre, doublement pénalisé, tout en ayant été privé de toute faculté de faire valoir ses droits. En outre, bien que la jurisprudence se montre restrictive quant à la recevabilité d'une demande de révision ayant pour objet une ordonnance pénale (cf. supra consid. 3.3), celle-ci suppose, pour imputer au requérant un comportement abusif, que l'intéressé ait renoncé en connaissance de cause à faire valoir ses moyens par le biais de l'opposition, avant de revenir sur cette position pour formuler une demande de révision. Or, le jugement attaqué ne comporte aucune constatation permettant de retenir une telle configuration s'agissant de l'ordonnance pénale du 28 mai 2018, sans compter qu'une telle hypothèse apparaît en réalité exclue du fait même de l'application de l'<ref-law>. C'est donc à tort que la cour cantonale a retenu que le recourant avait agi de façon abusive pour déclarer sa demande irrecevable. Ses griefs s'avèrent par conséquent fondés sur ce point. Force est au demeurant de relever que la cour cantonale passe entièrement sous silence les allégations du recourant concernant l'existence d'un droit de séjourner en Suisse dès novembre 2017 lorsqu'elle retient, dans une motivation évoquée par surabondance, que son statut administratif avec effet au 5 novembre 2018 ne pouvait constituer un motif de révision en rapport avec un séjour illégal constaté en date du 22 avril 2018. Compte tenu du sort des griefs soulevés par le recourant dans ce contexte et de l'absence de grief de violation du droit d'être entendu sur ce point, il n'y a pas lieu d'examiner la question plus avant.
4.2. En ce qui concerne l'ordonnance pénale du 10 janvier 2019, il ressort certes du jugement attaqué que cette dernière a été valablement notifiée par pli recommandé. Pour autant, il apparaît également que l'ordonnance en question a été rendue directement, sans ouverture formelle d'instruction. Pour ce même motif et compte tenu du lien étroit entre les deux ordonnances pénales en cause, il y a lieu d'admettre que les circonstances excluaient ici aussi d'imputer au recourant un comportement abusif, nonobstant les carences procédurales qu'il doit se voir opposer. Ses griefs sont donc aussi fondés dans cette mesure.
5.
Dans un dernier grief, le recourant se plaint d'une violation de l'<ref-law> et reproche à la cour cantonale de lui avoir refusé la désignation d'un défenseur d'office.
Au vu des éléments précités et compte tenu des spécificités procédurales de la présente cause, on ne saurait suivre la cour cantonale lorsqu'elle retient que dite cause était de peu de gravité et ne présentait pas de difficultés insurmontables pour un requérant agissant seul. Le grief doit être admis.
6.
Il résulte de ce qui précède que le recours doit être admis, l'arrêt attaqué annulé et la cause renvoyée à l'autorité cantonale pour nouvelle décision. Le recourant, qui obtient gain de cause, ne supportera pas de frais judiciaires (<ref-law>) et a droit à des dépens à la charge du canton de Vaud (<ref-law>). La demande d'assistance judiciaire devient ainsi sans objet.

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis, le jugement attaqué est annulé et la cause est renvoyée à la cour cantonale pour nouvelle décision.
2.
Il n'est pas perçu de frais judiciaires.
3.
Le canton de Vaud versera au mandataire du recourant une indemnité de 3'000 fr. à titre de dépens pour la procédure devant le Tribunal fédéral.
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 28 mai 2020
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
Le Greffier : Dyens