Faits :
A.
Par jugement du 7 juillet 2013, le Tribunal correctionnel de l'arrondissement de Lausanne a condamné X._ pour lésions corporelles simples, tentative de viol et infraction à la LEtr (RS 142.20) à une peine privative de liberté de trois ans, sous déduction de 274 jours de détention avant jugement. Le tribunal a également constaté que X._ avait été détenu durant neuf jours dans des conditions de détention illicites et ordonné que cinq jours de détention soient réduits de la peine fixée, à titre de réparation du tort moral subi.
B.
Statuant le 15 décembre 2015, la Cour d'appel pénale du Tribunal cantonal vaudois a rejeté l'appel de X._ et confirmé le jugement précité.
C.
X._ forme un recours en matière pénale au Tribunal fédéral contre ce jugement, concluant, avec suite de frais et dépens, principalement à sa réforme en ce sens qu'une indemnité de 450 fr. lui est versée et, subsidiairement, que neuf jours sont déduits de la peine prononcée en compensation du tort moral. Plus subsidiairement, il conclut à son annulation et au renvoi de la cause à l'autorité précédente pour nouvelle décision. Il sollicite également l'assistance judiciaire.

Considérant en droit :
1.
Le recourant conteste la décision cantonale de lui allouer une réparation pour le tort moral découlant de la détention dans des conditions illicites sous la forme d'une réduction de la peine à laquelle il a été condamné. Il soutient, d'une part, que l'interprétation de l'<ref-law> selon les règles applicables en la matière ne permettrait pas de compenser son tort moral autrement que par une indemnité financière. Il fait valoir, d'autre part, que l'autorité précédente ne pouvait réparer son tort moral en procédant à une réduction de peine, alors qu'il avait conclu à une indemnisation pécuniaire à hauteur de 450 francs.
1.1. Aux termes de l'<ref-law>, si le prévenu a, de manière illicite, fait l'objet de mesures de contrainte, l'autorité pénale lui alloue une juste indemnité et réparation du tort moral.
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 (<ref-ruling> consid. 2.5.1 p. 250). 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 donc en principe intervenir et celui-ci n'a pas pour conséquence la remise en liberté du prévenu (<ref-ruling> 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'<ref-law> ou, cas échéant, par une réduction de la peine (arrêt 6B_876/2015 du 2 mai 2016 consid. 4.1 destiné à la publication et les réf. citées).
S'agissant du mode et de l'étendue de l'indemnisation fondée sur les <ref-law>, il n'est pas exclu de s'inspirer des règles générales des <ref-law>. Ces dispositions accordent au juge un large pouvoir d'appréciation, que le Tribunal fédéral ne revoit qu'avec retenue. En vertu de l'<ref-law>, une réparation en nature n'est pas exclue (arrêt 6B_876/2015 du 2 mai 2016 consid. 4.1 destiné à la publication et les réf. citées).
Dans l'arrêt précité, le Tribunal fédéral a relevé que le mode et l'étendue de la réparation étaient laissés à l'appréciation du juge, et ce, indépendamment des conclusions prises par le prévenu tendant à l'allocation d'une indemnisation financière au sens de l'<ref-law> (cf. arrêt 6B_876/2015 du 2 mai 2016 consid. 4.3 destiné à la publication). Cette jurisprudence s'applique immédiatement (cf. <ref-ruling> consid. 3.2 p. 85; arrêt 6B_310/2014 du 23 novembre 2015 consid. 4.3). Le recourant n'avance aucun argument qui n'aurait pas déjà été pris en compte.
1.2. Il découle de ce qui précède que le choix du mode de compensation n'appartient pas au recourant, mais est laissé à l'appréciation du juge. Cela étant, on ne saurait reprocher à la cour cantonale - et le recourant ne le prétend pas - d'avoir excédé son pouvoir d'appréciation en considérant que la restitution de la liberté constituait le meilleur moyen de réparer le tort subi par l'intéressé et d'avoir opté pour une indemnisation sous la forme d'une réduction de peine, ce qui correspond à une indemnisation en nature. Le mode de réparation choisi par la cour cantonale échappe par conséquent à la critique. Le grief est rejeté.
2.
Le recourant soutient ensuite que la réduction de peine accordée serait insuffisante. Il ajoute que rien ne permettrait de justifier une différence de traitement entre sa situation et celle d'un détenu acquitté, dont l'exécution de la détention était licite. Il se plaint également d'une motivation incomplète sur ce dernier point.
2.1. La cour cantonale a exposé qu'une réduction de peine quantitativement équivalente au nombre de jours passés en détention n'était pas appropriée, l'incarcération étant justifiée dans son principe; pour tenir compte de la pénibilité accrue d'une telle détention, une réduction d'un jour de peine pour deux jours de détention dans des conditions illicites au-delà des premières 48 heures était adéquate. Elle a ainsi considéré qu'on ne pouvait, dans le cas d'espèce, déduire un jour de détention par jour de détention subie dans des conditions illicites, dès lors que ce n'était pas l'incarcération du recourant en elle-même qui était injustifiée, mais uniquement les conditions dans lesquelles elle s'était déroulée. Partant, elle a jugé que la réduction de la peine privative de liberté de cinq jours à titre de réparation du tort moral opérée par les premiers juges s'avérait adéquate et devait être confirmée.
2.2. L'indemnisation en raison des conditions de détention illicites fait appel au pouvoir d'appréciation du juge; le Tribunal fédéral n'intervient dès lors qu'avec retenue (cf. supra consid. 1.1). L'ampleur de la réparation dépend avant tout de l'appréciation concrète des circonstances particulières de l'espèce, en particulier de la gravité des souffrances physiques ou psychiques consécutives à l'atteinte subie (cf. sur la réparation financière, <ref-ruling> consid. 2.2.2 p. 309 s.).
2.3. En l'espèce, il ne ressort pas du jugement attaqué que le recourant aurait spécialement mal vécu sa détention dans des conditions illicites ni qu'elle lui aurait causé des souffrances particulières justifiant une réduction supérieure à celle accordée par la cour cantonale, et le recourant n'établit pas que l'absence d'une telle constatation de fait serait arbitraire. Il se limite à affirmer que la réduction de peine octroyée serait insuffisante, en ce sens qu'il se justifierait de retenir, dans l'esprit de l'<ref-law>, une réduction d'un jour de peine pour un jour de détention dans des conditions illicites. De la sorte, il ne s'emploie pas à établir en quoi la cour cantonale aurait abusé de son large pouvoir d'appréciation en la matière. De plus, on peut admettre, contrairement à ce qu'il affirme, qu'une période de détention injustifiée, dans des conditions licites, porte davantage atteinte au prévenu qu'une détention dans des conditions illicites, la privation de liberté étant, dans ce dernier cas, légitime (cf. arrêt 6B_1057/2015 du 25 mai 2016 consid. 5.3.3). En définitive, les critiques du recourant ne laissent pas apparaître que la juridiction cantonale aurait abusé de son pouvoir d'appréciation en considérant que la réduction de cinq jours de la peine privative de liberté réparait suffisamment le tort moral subi par le prénommé en raison des conditions dans lesquelles son incarcération s'était déroulée. Il n'y a ainsi pas lieu de la remettre en cause.
Pour le surplus, la motivation cantonale permet de comprendre les raisons qui ont amené les juges à réduire la peine dans cette proportion et le recourant a pu attaquer ce point devant le Tribunal fédéral en toute connaissance de cause.
Les griefs soulevés par le recourant sont en conséquence rejetés, dans la mesure de leur recevabilité.
3.
Sur le vu de ce qui précède, le recours doit être rejeté dans la mesure où il est recevable. Il n'était cependant pas dénué de toute chance de succès. En outre, la nécessité pour l'intéressé de recourir aux services d'un avocat ne fait pas de doute. L'assistance judiciaire doit par conséquent être accordée au recourant, qui ne dispose pas de ressources suffisantes (art. 64 al. 1 et 2 LTF).

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 admise et Me Loïc Parein, avocat à Lausanne, est désigné en qualité de conseil d'office de X._.
3.
Il n'est pas perçu de frais judiciaires.
4.
La Caisse du Tribunal fédéral versera une indemnité de 3000 fr. à Me Loïc Parein au titre de l'assistance judiciaire.
5.
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 1er décembre 2016
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
La Greffière : Nasel