Faits : A. Dans le cadre d'une procédure pénale ouverte à l'encontre de X._, le Ministère public de la République et canton de Genève a rendu une ordonnance de non-entrée en matière le 5 novembre 2015 dans laquelle il refuse d'allouer à ce dernier une indemnité pour ses frais d'avocat et pour la privation de liberté subie. B. Statuant par arrêt du 17 mars 2016 sur le recours formé par X._ contre l'ordonnance précitée, la Chambre pénale de recours de la République et du canton de Genève l'a rejeté. En bref, il en ressort les faits suivants. Le 30 mai 2015 (cf. art. 105 al. 2 LTF), à 10h, X._, ressortissant turc domicilié en Turquie, a été appréhendé par les gardes-frontière lors de son entrée en Suisse, au passage frontière de Ferney-Voltaire, au volant d'un véhicule immatriculé à Genève et dont la détentrice est A._. Lors du contrôle de son permis de conduire, les gardes-frontière ont constaté qu'il s'agissait d'une contrefaçon d'un permis de conduire turc. A 10h37, à la suite d'un contrôle positif à la cocaïne, les agents ont fait appel à la brigade canine. La fouille corporelle s'est révélée négative. Ils ont ensuite, à 13h30, demandé l'envoi d'une patrouille. A 13h55, X._ a été remis à une patrouille de gendarmerie pour la suite de la procédure et le ministère public a été avisé de l'arrestation provisoire à 14h48. X._ a été auditionné par les gendarmes de 15h28 à 17h04. Il a été libéré à 17h25 et son permis de conduire transmis à la Brigade de police technique et scientifique (ci-après: BPTS) pour analyse. Le 11 juin 2015, X._ a retourné au bureau de police, visiblement par l'intermédiaire de A._, le formulaire relatif à sa situation personnelle et divers documents. A teneur du rapport du 12 août 2015 de la BPTS, le permis de conduire de X._ ne présentait aucun signe de falsification et les autorités turques avaient confirmé avoir émis ledit document. Le 15 juin 2015, X._ avait déclaré avoir perdu son permis de conduire et avait obtenu la délivrance d'un nouveau document. Par ordonnance « fichet » du 14 septembre 2015, le ministère public a décidé de ne pas entrer en matière sur les faits, en application de l'art. 310 al. 1 let. a CPP, avec la mention « pas d'infraction ». C. X._ forme un recours en matière pénale au Tribunal fédéral contre l'arrêt du 17 mars 2016 et conclut, avec suite de dépens, à l'allocation en sa faveur d'une indemnité équitable de 500 fr. pour la privation de liberté subie et d'une indemnité de 2'600 fr. pour les frais d'avocat encourus pour la procédure cantonale. Il sollicite par ailleurs l'assistance judiciaire et la désignation de son conseil en qualité d'avocat d'office. Invitée à se déterminer sur le recours, la cour cantonale, se référant aux considérants de son arrêt, y a renoncé. Le ministère public a conclu au rejet. Le recourant a répliqué.