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 (<ref-law>) 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é.

Considérant en droit :
1.
Le recourant conteste le refus de lui allouer une indemnité pour ses frais de défense. Il invoque une violation du droit fédéral dans l'application des <ref-law> et 430 al. 1 let. a CPP ainsi qu'une violation de la présomption d'innocence.
1.1. Selon l'<ref-law>, le prévenu acquitté totalement ou en partie ou mis au bénéfice d'un classement a droit à une indemnité notamment pour ses dépenses occasionnées par l'exercice raisonnable de ses droits de procédure (let. a). L'autorité pénale peut réduire ou refuser l'indemnité lorsque le prévenu a provoqué illicitement et fautivement l'ouverture de la procédure ou a rendu plus difficile la conduite de celle-ci (<ref-law>). L'<ref-law> est le pendant de la règle énoncée à l'<ref-law> en matière de frais. Cette dernière disposition prévoit qu'en cas d'ordonnance de classement ou d'acquittement, tout ou partie des frais de la procédure peuvent être mis à la charge du prévenu, s'il a, de manière illicite et fautive, provoqué l'ouverture de la procédure ou rendu plus difficile la conduite de celle-ci (arrêt 6B_77/2013 du 4 mars 2013 consid. 2.3).
La question de l'indemnisation du prévenu (<ref-law>) doit être traitée en relation avec celle des frais (<ref-law>). Si le prévenu supporte les frais en application de l'art. 426 al. 1 ou 2 CPP, une indemnité est en règle générale exclue. En revanche, si l'Etat supporte les frais de la procédure pénale, le prévenu dispose d'un droit à une indemnité pour ses frais de défense et son dommage économique ou à la réparation de son tort moral selon l'<ref-law>; dans ce cas, il ne peut être dérogé au principe du droit à l'indemnisation qu'à titre exceptionnel (<ref-ruling> consid. 2.4.2 p. 357; arrêt 6B_262/2015 du 29 janvier 2016 consid. 1.2). La question de l'indemnisation doit ainsi être tranchée après la question des frais. Dans cette mesure, la décision sur les frais préjuge de la question de l'indemnisation (arrêts 6B_620/2016 du 17 mai 2017 consid. 2.2.2; 6B_203/2015 du 16 mars 2016 consid. 1.2 et 1.6; 6B_262/2015 du 29 janvier 2016 consid. 1.2).
1.2. La cour cantonale considère que, comme le ministère public a toute latitude dans l'application de l'<ref-law>, il demeure libre de refuser d'allouer une indemnité en application de l'<ref-law>. Il est communément admis que l'<ref-law> définit une " Kannvorschrift " en ce sens que le juge n'a pas l'obligation de faire supporter tout ou partie des frais au prévenu libéré des fins de la poursuite pénale, même si les conditions d'une imputation sont réalisées (Moreillon/Parein-Reymond, Petit commentaire, Code de procédure pénale, 2 e éd. 2016, n° 10 ad <ref-law> et les réf. cit.). Cette faculté laissée au ministère public n'a pas de portée sur le principe de procédure sus-énoncé, sauf à le vider de son sens. Dans le cas présent, le ministère public a libéré le recourant des frais de procédure à la suite de sa décision de classement de la procédure ouverte à l'encontre du recourant pour tous les chefs d'accusation. Sa décision sur les frais a ainsi préjugé la question du droit à l'indemnité, quel que soit le motif qui l'a conduit à renoncer à percevoir des frais de procédure. Il appartenait ainsi à la cour cantonale d'examiner la prétention du recourant pour ses frais de défense relatifs à son avocat de choix pour la procédure cantonale en application de l'<ref-law> (voir dans ce sens, arrêt 6B_262/2015 du 29 janvier 2016 consid. 1.4). Ne l'ayant pas fait, elle a violé le droit fédéral.
1.3. Au demeurant, les motifs avancés par la cour cantonale pour refuser l'indemnité violent le droit fédéral. Selon la jurisprudence relative à l'<ref-law>, applicable par analogie à l'<ref-law> (arrêt 6B_256/2016 du 20 juin 2016 consid. 3.1), la condamnation d'un prévenu acquitté à supporter tout ou partie des frais, respectivement le refus de lui allouer une indemnisation à raison du préjudice subi par la procédure pénale, doit respecter la présomption d'innocence, consacrée par les <ref-law>, 32 al. 1 Cst. et 6 par. 2 CEDH. Celle-ci interdit de rendre une décision défavorable au prévenu libéré en laissant entendre que ce dernier serait néanmoins coupable des infractions qui lui étaient reprochées. Une condamnation aux frais, respectivement un refus d'indemnisation, n'est ainsi admissible que si le prévenu a provoqué l'ouverture de la procédure pénale dirigée contre lui ou s'il en a entravé le cours. A cet égard, seul un comportement fautif et contraire à une règle juridique, qui soit en relation de causalité avec les frais imputés, respectivement le refus de l'indemnisation, entre en ligne de compte. Pour déterminer si le comportement en cause est propre à justifier l'imputation des frais ou le refus d'une indemnité, le juge peut prendre en considération toute norme de comportement écrite ou non écrite résultant de l'ordre juridique suisse pris dans son ensemble, dans le sens d'une application par analogie des principes découlant de l'<ref-law> (<ref-ruling> consid. 1b p. 334 et les réf. citées). Le comportement en question doit en outre se trouver dans une relation de causalité adéquate avec l'ouverture de l'enquête ou les obstacles mis à celle-ci (<ref-ruling> consid. 2c p. 170 s.; plus récemment arrêt 6B_262/2015 du 29 janvier 2016 consid. 1.1). La relation de causalité est établie lorsque, selon le cours ordinaire des choses et l'expérience de la vie, le comportement de la personne concernée était de nature à provoquer l'ouverture de la procédure pénale et le dommage ou les frais que celle-ci a entraînés (<ref-ruling> consid. 2c p. 170; arrêt 6B_203/2015 du 16 mars 2016 consid. 1.1). Une condamnation aux frais ne peut se justifier que si, en raison du comportement illicite du prévenu, l'autorité était légitimement en droit d'ouvrir une enquête. Elle est en tout cas exclue lorsque l'autorité est intervenue par excès de zèle, ensuite d'une mauvaise analyse de la situation ou par précipitation (<ref-ruling> consid. 2c p. 171; arrêt 6B_262/2015 du 29 janvier 2016 consid. 1.1).
La cour cantonale a motivé sa décision de refus d'indemnité en lien avec l'infraction à la LStup en se fondant sur les charges qui ont donné lieu à l'interpellation du recourant pour considérer que c'était le comportement suspect du recourant qui avait motivé l'ouverture d'une procédure pénale. Par ce raisonnement, elle n'expose pas en quoi le recourant aurait transgressé une règle de comportement de l'ordre juridique autre que celle se rapportant au soupçon d'avoir violé la LStup, dont il a été libéré. S'agissant de l'infraction à la LEtr, l'ordonnance de classement se fonde sur un précédent acquittement prononcé par la Chambre pénale d'appel et de révision en date du 27 mai 2016 dont a bénéficié le recourant pour le même chef d'accusation motivé par la circonstance que les autorités administratives n'ont pas fait usage des mesures idoines pour mener une procédure de renvoi à son terme. Il n'y a donc pas lieu de considérer que le recourant a provoqué la nouvelle procédure qui devait conduire irrémédiablement à son classement au vu de ce précédent.
2.
Le recourant demande que les indemnités dues au titre de ses frais de défense soient versées directement en main de son conseil. Il y a lieu d'examiner la recevabilité de ses conclusions sous cet angle.
2.1. Le Tribunal fédéral, qui s'est prononcé sur la question dans l'arrêt 6B_802/2015 du 9 décembre 2015 consid. 9, a exposé que le CPP, pour la défense de choix, ne prévoyait pas que les indemnités de frais de défense dues au prévenu acquitté ou au bénéfice d'un classement en application de l'<ref-law>, puissent être versées directement à son avocat, dont les honoraires avaient du reste peut-être déjà été réglés au moment du prononcé de la décision d'indemnisation. Il n'y avait pas lieu de suivre les auteurs qui préconisaient cette approche (Wehrenberg/Frank, in: NIGGLI/HEER/ WIPRÄCHTIGER [éd.], Basler Kommentar, Schweizerische Strafprozessordnung/Jugendstrafprozessordnung, 2e éd. 2014, n° 21 s. ad <ref-law>; voir aussi Pitteloud, Code de procédure pénale suisse, 2012, n° 1350 in fine ad <ref-law>). Il n'y a pas de motif de s'écarter de la jurisprudence et le recourant n'en fait pas valoir. Il y a lieu de préciser que le prévenu est seul titulaire de la créance en paiement de ses frais de défense envers l'Etat. La jurisprudence a rappelé à propos de l'<ref-law>, qui prévoit que les autorités pénales peuvent compenser les créances portant sur des frais de procédure avec les indemnités accordées à la partie débitrice dans la même procédure pénale et avec des valeurs séquestrées, que cette disposition est susceptible de s'appliquer dans l'hypothèse où le prévenu a été acquitté en tout ou partie et qu'il peut prétendre à une indemnisation sur la base de l'art. 429 al. 1 let. a ou b CPP, alors qu'il doit simultanément supporter des frais de procédure selon l'<ref-law>, étant rappelé qu'une compensation est exclue en cas d'indemnité pour tort moral selon l'art. 429 al. 1 let. c CPP (arrêt 6B_648/2016 du 4 avril 2017 consid. 1 et renvoi à l'<ref-ruling> consid. 5 p. 244 s.).
2.2. Le recourant n'est ainsi pas admis à conclure au paiement des indemnités en faveur de son conseil. Ses conclusions ne sont toutefois pas irrecevables dès lors qu'il y a lieu de les interpréter dans le sens qu'il réclame l'indemnité en sa faveur.
3.
Le recours doit être admis, l'arrêt attaqué annulé et la cause renvoyée à la cour cantonale afin qu'elle statue sur l'indemnité due au recourant pour la procédure devant le ministère public ainsi que sur les frais et indemnité de la procédure de recours. Le recourant qui obtient gain de cause peut prétendre à des dépens pour la procédure devant le Tribunal fédéral (<ref-law>). La demande d'assistance est sans objet dans cette mesure (64 al. 2 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis, l'arrêt attaqué est annulé et la cause renvoyée à la cour cantonale pour nouvelle décision dans le sens des considérants.
2.
Il est statué sans frais.
3.
Le canton de Genève versera une indemnité de 3'000 fr. en mains du conseil du recourant à 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 de justice de la République et canton de Genève, Chambre pénale de recours.
Lausanne, le 14 juillet 2017
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
Le Greffier : Dyens