Faits: A. Par ordonnance du 17 décembre 2012, le Ministère public du canton de Genève a prononcé le classement partiel de la procédure instruite contre A._ en tant qu'elle portait sur l'infraction de blanchiment d'argent (ch. 1 dispositif), refusé la levée des séquestres (ch. 2 dispositif) et dit que le sort des fonds séquestrés, des frais et indemnités serait tranché par le juge du fond (ch. 3 dispositif). Parallèlement, A._ a été renvoyé devant le Tribunal correctionnel genevois pour tentative d'instigation à assassinat, tentative d'instigation à lésions corporelles graves et infractions à la LEtr. Le jugement rendu par le Tribunal correctionnel le 1 er mars 2013 a fait l'objet d'un appel. Statuant sur le recours formé par A._ contre l'ordonnance du 17 décembre 2012, la Chambre pénale de recours de la Cour de justice genevoise l'a admis par arrêt du 8 février 2013, a annulé le ch. 3 du dispositif de l'ordonnance de classement. Elle a retenu que les frais de la procédure ne pouvaient être mis à la charge de A._, faute de réalisation des conditions posées à l'art. 426 al. 2 CPP. Dès lors, le séquestre d'espèces ne pouvait être maintenu à ces fins. B. Le 31 janvier 2013, A._ a présenté au Ministère public une demande d'indemnisation fondée sur l'art. 429 CPP. Par décision du 19 mars 2013, le Ministère public genevois a refusé la demande d'indemnisation de A._. Par arrêt du 18 juin 2013, la Chambre pénale de recours de la Cour de justice genevoise a rejeté le recours formé par A._. C. A._ forme un recours en matière pénale au Tribunal fédéral contre cet arrêt. Il conclut, avec suite de frais et dépens, à la réforme de celui-ci en ce sens qu'il doit être indemnisé à la suite du classement de la procédure du chef de blanchiment d'argent et au renvoi de la cause à l'autorité précédente pour nouvelle décision au sens des considérants. Il requiert par ailleurs l'assistance judiciaire. Invités à déposer des observations sur le recours, la cour cantonale y a renoncé, cependant que le Ministère public a conclu à son rejet. A._ s'est déterminé sur ces écritures par courrier du 6 mai 2014, lequel a été communiqué à titre de renseignement au Ministère public le 8 mai 2014. 