Faits: A. Le Tribunal de police du canton de Genève a, par jugement du 11 janvier 2013, condamné X._ à une peine privative de liberté de 7 mois, sous déduction de 185 jours de détention avant jugement, ainsi qu'à une amende de 300 francs assortie du prononcé d'une peine privative de liberté de substitution de 3 jours, pour séquestration et enlèvement (art. 183 ch. 1 CP), tentative d'extorsion et chantage (art. 22 al. 1 et 156 ch. 1 CP), violation de domicile (art. 186 CP) et voies de fait (art. 126 al. 1 CP). Il l'a acquitté des chefs d'encouragement à la prostitution (art. 195 al. 2 et 3 CP), de tentative de contrainte (art. 22 al. 1 et 181 CP) et de vol d'importance mineure (art. 139 ch. 1 et 172 ter al. 1 CP). Le maintien en détention pour des motifs de sûreté de X._ a été ordonné. Le 17 janvier 2013, une des parties plaignantes a annoncé son appel à l'encontre du jugement, en raison des acquittements partiels prononcés par le Tribunal de police. X._ n'a pas formé d'appel joint. Par ordonnance du 21 janvier 2013, le Tribunal des mesures de contrainte du canton de Genève (Tmc) a refusé la libération demandée par X._ le 15 janvier 2013. Par ordonnance du 28 janvier 2013, le Tmc a prolongé la détention pour des motifs de sûreté jusqu'au 28 avril 2013, au vu de l'appel interjeté par la partie plaignante et du risque du prononcé d'une peine plus sévère. Parallèlement aux procédures de recours initiées contre les ordonnances des 21 et 28 janvier 2013 devant la Chambre pénale de recours de la Cour de justice genevoise, tendant notamment à l'allocation d'indemnités et de dépens, X._ a déposé, le 5 février 2013, une nouvelle demande de libération immédiate. A cette même date, il avait exécuté l'intégralité de la peine prononcée à son encontre en première instance. B. Par ordonnance du 22 février 2013, la Chambre pénale d'appel et de révision a ordonné la libération immédiate de X._ et a déclaré sa demande tendant à l'indemnisation de sa détention injustifiée, non légitime et prématurée. Par arrêt 1B_129/2013 du 26 juin 2013, le Tribunal fédéral a déclaré le recours, formé contre cette ordonnance, irrecevable, faute d'intérêt pratique et actuel du recourant. A teneur de l'arrêt, le juge du fond compétent en matière d'allocations d'indemnités était saisi à la suite de l'appel formé par la partie plaignante, et disposait d'éléments suffisants pour apprécier cette question. C. Par jugement du 30 août 2013, la Chambre pénale d'appel et de révision de la Cour de justice a rejeté l'appel formé par la partie plaignante contre le jugement du Tribunal de police et a débouté X._ de ses conclusions en indemnisation. D. X._ interjette un recours en matière pénale auprès du Tribunal fédéral contre cette décision, dans la mesure où la cour cantonale le déboute de ses conclusions en indemnisation. Il conclut, sous suite de frais et dépens, principalement à sa réforme en ce sens que l'Etat de Genève soit condamné à lui verser une indemnité de 200 francs par jour de détention injustifiée, soit 6'400 francs, avec intérêts à 5% l'an à compter du 6 février 2013. Subsidiairement, il conclut à l'annulation du jugement cantonal et au renvoi de la cause à l'autorité de deuxième instance pour nouvelle décision dans le sens des considérants. Il sollicite en outre l'assistance judiciaire. Invités à se déterminer, la cour cantonale et le Ministère public ont renoncé à formuler des observations.