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.