Faits : A. X._ a été interpellé par la police le 16 septembre 2015. Il lui était reproché d'avoir procédé à la vente d'une boulette de cocaïne à un toxicomane pour la somme de 80 fr. et d'avoir séjourné en Suisse sans être au bénéfice d'une autorisation de séjour du 23 mai au 2 novembre 2015. Par ordonnance du 29 juin 2016, le Ministère public de la République et canton de Genève a classé la procédure pénale ouverte contre X._ du chef d'infractions à l'art. 19 al. 1 de la loi fédérale sur les stupéfiants (LStup) et à l'art. 115 al. 1 let. b de la loi fédérale sur les étrangers (LEtr). A l'appui de sa décision, le ministère public a relevé le défaut de prévention s'agissant de la vente de stupéfiants (art. 319 al. 1 let. a CPP) et un empêchement de procéder (art. 319 al. 1 let. d CPP) relatif au séjour illégal du fait que l'on ne pouvait pas considérer que la procédure administrative pour l'exécution du renvoi de l'intéressé avait été menée à son terme avec succès. Le Ministère public, dans la même ordonnance, a laissé les frais de procédure à la charge de l'Etat mais a refusé d'indemniser le prévenu pour ses frais de défense. B. Par arrêt du 5 septembre 2016, la Chambre pénale de recours de la Cour de justice du canton de Genève a rejeté le recours formé par X._ contre l'ordonnance de classement du 4 juillet 2016 portant sur le refus d'indemnisation de ses frais de défense. C. X._ forme un recours en matière pénale contre la décision cantonale et conclut, principalement, à son annulation et à la condamnation de l'Etat de Genève à verser à son conseil une indemnité de 3'456 fr. à titre d'indemnité pour les dépenses occasionnées par l'exercice de ses droits de procédure ainsi qu'une indemnité de 1'800 fr. pour ses frais de défense devant la Chambre pénale de recours. Subsidiairement, il conclut à l'annulation de l'arrêt attaqué et à son renvoi à l'autorité cantonale afin qu'elle statue dans le sens des considérants. Il sollicite en outre le bénéfice de l'assistance judiciaire. D. Invités à se déterminer, le ministère public a conclu au rejet du recours, tandis que la cour cantonale a indiqué se référer aux considérants de son arrêt. Les observations du ministère public et la prise de position de la cour cantonale ont été communiquées au recourant, qui n'a pas répliqué.