Faits :
A.
A.a. X._ a été appréhendé le 23 octobre 2013 et une enquête pénale a été ouverte contre lui pour vol, tentative de vol, dommages à la propriété, recel et violation de domicile. Par ordonnance du 25 octobre 2013, le Tribunal des mesures de contrainte a ordonné la détention provisoire de X._ pour une période de trois mois et, par ordonnance du 13 novembre 2013, a constaté que les conditions dans lesquelles s'était déroulée la détention provisoire de X._ au Centre d'intervention régionale (CIR) et au CIR Ouest du 23 octobre au 13 novembre 2013 y compris, soit durant 22 jours, n'étaient pas conformes aux dispositions légales applicables en la matière et a donné l'ordre de transférer immédiatement l'intéressé dans un établissement avant jugement. Par ordonnance pénale du 13 mars 2014, le Ministère public cantonal Strada a condamné X._ à une peine privative de liberté de 180 jours, sous déduction de 142 jours de détention subis avant jugement. Le même jour, X._ a été libéré et raccompagné à la frontière française.
A.b. Par courrier adressé le 17 mars 2014 au Procureur cantonal Strada, X._ a requis qu'il soit statué sur l'indemnité qui lui était due en raison des conditions illicites de sa détention. Par prononcé du 31 mars 2014, le Ministère public cantonal Strada a refusé de donner suite à la requête de X._ au motif que celle-ci était tardive. Le 13 juin 2014, la Chambre des recours pénale du Tribunal cantonal a annulé le prononcé du 31 mars 2014, considérant que le Ministère public cantonal Strada aurait dû statuer d'office sur la requête en indemnisation de X._ en rendant son ordonnance de condamnation du 13 mars 2014, qu'une procédure ultérieure indépendante au sens des art. 363 ss CPP devait être envisagée et que la décision du 31 mars 2014 aurait dû prendre la forme d'une ordonnance pénale susceptible d'opposition.
A.c. Par décision ultérieure à une ordonnance pénale du 18 février 2015, le Ministère public cantonal Strada a modifié l'ordonnance pénale du 13 mars 2014 en ce sens qu'il a condamné X._ à une peine privative de liberté de 180 jours, sous déduction de 142 jours de détention préventive avant jugement, a constaté que X._ avait subi 22 jours de détention dans des conditions illicites et a ordonné que la peine à exécuter soit réduite de 11 jours, à titre de réparation morale. Le 2 mars 2015, X._ a formé opposition à cette ordonnance, concluant à sa réforme en ce sens qu'une indemnité pécuniaire d'un minimum de 100 fr. par jour pour les 22 jours de détention illicite lui est accordée en réparation du tort moral subi par les conditions illicites de détention. Par prononcé du 11 juin 2015, le Tribunal de police de l'arrondissement de Lausanne a admis l'opposition formée par X._ et a dit que l'État de Vaud lui devait immédiat paiement du montant de 1000 fr. à titre de réparation du tort moral.
B.
Statuant le 8 octobre 2015, la Cour d'appel pénale du Tribunal cantonal a admis l'appel du Ministère public cantonal Strada et rejeté l'appel joint formé par X._ contre le prononcé du 11 juin 2015 du Tribunal de police de l'arrondissement de Lausanne sollicitant une indemnité de 4'400 francs. Elle a réformé ce prononcé en ce sens que l'opposition formée par X._ contre la décision ultérieure à une ordonnance pénale rendue le 18 février 2015 par le Ministère public cantonal Strada était rejetée.
C.
X._ forme un recours en matière pénale au Tribunal fédéral contre cet arrêt. Il conclut principalement et avec suite de frais et dépens au paiement d'un montant de 4'400 fr. plus intérêts au taux de 5% l'an courant dès le 13 mars 2014, à titre de réparation du tort moral pour la détention subie dans des conditions illicites. A titre subsidiaire, il conclut à l'annulation du jugement entrepris et au renvoi de la cause à la cour cantonale pour nouvelle décision dans le sens des considérants. X._ requiert, par ailleurs, le bénéfice de l'assistance judiciaire.
D.
Invités à se déterminer sur le recours, le Ministère public n'a pas répondu dans le délai imparti et la Cour d'appel pénale du Tribunal cantonal y a renoncé, se référant aux considérants du jugement entrepris.
Considérant en droit :
1.
Le recourant conteste la décision de la cour cantonale de lui allouer une réparation pour le tort moral découlant de la détention provisoire dans des conditions illicites sous la forme d'une réduction de la peine à laquelle il a été condamné. Il sollicite en lieu et place une indemnisation pécuniaire à hauteur de 200 fr. par jour de détention dans des conditions illicites, soit 4'400 fr. au total.
Le recours en matière pénale est ouvert contre les décisions relatives aux conditions de la détention provisoire ou pour des motifs de sûreté (art. 78 al. 1 LTF; ATF 137 IV 22 consid. 1 p. 23).
2.
Selon la jurisprudence, lorsqu'une irrégularité constitutive d'une violation d'une garantie conventionnelle ou constitutionnelle a entaché la procédure relative à la détention provisoire, celle-ci peut être réparée par une décision de constatation (ATF 140 I 246 consid. 2.5.1 p. 250; ATF 138 IV 81 consid. 2.4 p. 85). Une telle décision vaut notamment lorsque les conditions de détention provisoire illicites sont invoquées devant le juge de la détention. A un tel stade de la procédure, seul un constat peut en principe intervenir et celui-ci n'a pas pour conséquence la remise en liberté du prévenu (ATF 139 IV 41 consid. 3.4 p. 45). Il appartient ensuite à l'autorité de jugement d'examiner les possibles conséquences des violations constatées, par exemple par le biais d'une indemnisation fondée sur l'art. 431 CPP ou, cas échéant, par une réduction de la peine (ATF 141 IV 349 consid. 2.1 p. 352; 140 I 246 consid. 2.5.1 p. 250; ATF 140 I 125 consid. 2.1 p. 128; ATF 139 IV 41 consid. 3.4 p. 45). Lorsque la personne détenue n'a formulé sa demande de constat et de réparation relative à ses conditions de détention avant jugement qu'après l'entrée en force du jugement pénal, la prétention du recourant à une réparation sous forme d'une réduction de la durée de sa peine privative de liberté entre en conflit avec l'autorité de chose jugée du jugement pénal, qui lie aussi les autorités chargées de son exécution. Sauf circonstances particulières, voire extraordinaires, dans cette hypothèse, la remise en liberté anticipée du condamné en exécution de peine ne peut, en règle générale, plus constituer une réparation du préjudice subi par celui-ci en raison de conditions de détention illicites (ATF 141 IV 349 consid. 2.2 p. 353 s.).
3.
La cour cantonale a jugé conforme au droit la réparation sous forme d'une réduction de la peine du recourant, accordée par le Ministère public par décision ultérieure à une ordonnance pénale entrée en force (art. 363 ss CPP). Elle a considéré que la jurisprudence de l'arrêt 6B_573/2015, publié aux ATF 141 IV 349, n'était pas directement transposable au cas d'espèce. Il s'agissait en effet du cas d'un détenu qui se plaignait, par une requête formulée après l'entrée en force du jugement pénal, de conditions illicites de détention avant et après son jugement, situation dans laquelle les autorités genevoises avaient considéré que la requête du détenu relevait de la compétence des autorités d'exécution de peine. Dans le cas présent, c'était bien l'autorité de jugement qui avait statué, sous la forme d'une décision judiciaire indépendante, sur l'indemnisation du prévenu. Cette procédure avait précisément pour but de modifier ou de compléter la sentence initiale, raison pour laquelle la décision était de la compétence de l'autorité judiciaire qui avait prononcé la condamnation. Au surplus, la requête d'indemnisation avait été formée avant que cette ordonnance pénale ne soit définitive et exécutoire. Aussi, rien n'empêchait le Ministère public d'accorder une réparation en nature.
4.
4.1. Le recourant objecte que la procédure des art. 363 ss CPP n'est applicable que lorsque des événements postérieurs au jugement imposent de modifier celui-ci. Il n'est pas compatible avec la sécurité du droit de modifier une peine entrée en force sans qu'un fait du condamné postérieur au jugement ne soit intervenu depuis lors. En revanche, la procédure de la décision ultérieure indépendante est envisageable s'il s'agit d'allouer une somme d'argent à titre de réparation morale, dans la mesure où cette forme d'indemnisation n'a pas d'effet sur la peine. Il en découle, selon lui, que seule une indemnisation pécuniaire pouvait lui être accordée.
4.2. Le Code pénal réserve la compétence de rendre certaines décisions, postérieurement à l'entrée en force du jugement, à l'autorité judiciaire, singulièrement lorsqu'il s'agit de modifier ou de compléter ce jugement en raison de circonstances tenant au comportement du condamné ou au processus d'exécution de la sanction ou d'une mesure (ex. : art. 36 al. 2 et al. 3 CP, art. 39, 46, 62a, 89, 60 al. 4, 62 al. 4, 62c al. 3 et al. 4, 63, 63b al. 4 et al. 5 CP, art. 64 al. 3 CP, etc.; arrêt 6B_1136/2015 du 18 juillet 2016 consid. 4.1 et les références citées). C'est ainsi le droit pénal matériel fédéral qui détermine quelles décisions ultérieures sont à la fois judiciaires et indépendantes. Sous cet angle, le Tribunal fédéral a récemment eu l'occasion de constater que la décision portant sur l'indemnisation à raison de conditions de détention avant jugement illicites ne constituait pas une décision judiciaire ultérieure indépendante au sens des art. 363 ss CPP (arrêt 6B_1136/2015 précité consid. 4.1). D'une part, cette problématique n'est, en effet, pas réglée par le Code pénal. Elle peut, d'autre part, en règle générale, être examinée au stade du jugement pénal, pour autant que le prévenu invoque ce moyen. Lorsque tel n'a pas été le cas, une éventuelle modification ou un complètement du jugement pénal ne résulterait, de toute manière, pas de circonstances tenant au comportement du condamné ou au processus d'exécution de la peine ou de la mesure. De surcroît, dans l'ATF 141 IV 349 précité, le Tribunal fédéral a exclu, sous réserve de circonstances particulières, voire extraordinaires, que le constat de conditions de détention illicites avant jugement puisse déboucher, après l'entrée en force du jugement pénal, sur une modification de celui-ci pour accorder une réduction de peine ou une libération conditionnelle anticipée (v. également : arrêts 6B_1136/2015 précité consid. 4.1; 6B_1071/2015 du 18 juillet 2016 consid. 2).
4.3. Il découle de ce qui précède que la procédure de décision judiciaire ultérieure indépendante au sens des art. 363 ss CPP a été suivie à tort par le Ministère public lorsqu'il a statué sur l'indemnisation des conditions de détention illicites. Contrairement à l'opinion de la cour cantonale, l'ATF 141 IV 349 est pertinent en l'espèce dans la mesure où la réparation du tort moral intervient après l'entrée en force de l'ordonnance condamnant le recourant à une peine privative de liberté. Que la requête d'indemnisation ait été formée après que l'ordonnance pénale a été rendue mais avant qu'elle devienne définitive et exécutoire n'y change rien, dans la mesure où cette requête n'a pas été considérée comme une opposition à l'ordonnance pénale, ce que le recourant n'a du reste pas prétendu. Faute d'opposition, l'ordonnance pénale du 13 mars 2014 infligeant une peine privative de liberté de 180 jours au recourant est entrée en force (cf. art. 354 al. 3 CPP), ce qui excluait d'accorder par décision ultérieure une réduction de peine à titre de réparation des conditions de détention illicites avant jugement.
4.4. Partant, il convient d'admettre le recours en tant qu'il conteste l'allocation d'une réparation du tort moral sous la forme d'une remise de peine. La question de savoir si l'autorité pouvait prononcer une remise de peine alors que le recourant était en liberté, ou encore si le recourant avait le choix du mode de compensation qu'il souhaitait, est dès lors sans objet. Au demeurant, sur ce deuxième point, la jurisprudence récente a constaté que le détenu ne bénéficie pas d'un tel choix, qui est laissé à l'appréciation du juge (voir en particulier l'arrêt 6B_876/2015 du 2 mai 2016, destiné à la publication). Cet aspect est cependant sans pertinence ici, une réduction de peine étant exclue (cf. supra consid. 4.3).
5.
La cause est renvoyée à la cour cantonale pour nouvelle décision. Elle statuera cas échéant sur l'indemnisation du recourant après avoir examiné sa compétence conformément au droit cantonal applicable. En effet, la procédure d'indemnisation à raison de conditions de détention avant jugement illicites alors que le jugement pénal est déjà en force n'est pas régie par les art. 363 ss CPP ou une autre disposition du CPP (cf. à Genève, arrêt 6B_1136/2015 du 18 juillet 2016 consid. 4).
Le recourant, qui obtient gain de cause, ne supportera pas de frais. Le canton de Vaud n'a pas non plus à en supporter (art. 66 al. 1 et 4 LTF). Le recourant a droit à des dépens à la charge du canton. Cela rend sans objet sa demande d'assistance judiciaire.
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 à l'autorité cantonale pour nouvelle décision.
2.
Il n'est pas perçu de frais judiciaires.
3.
Le canton de Vaud versera au conseil 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 23 septembre 2016
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
La Greffière : Musy