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'art. 94 CPP. 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é.