Faits : A. Par ordonnance du 15 octobre 2014, le Ministère public du canton de Genève a classé la procédure pénale ouverte à l'encontre de X._ pour infraction à la Loi fédérale sur les stupéfiants (art. 19 LStup) et infraction à la Loi fédérale sur les étrangers (art. 115 LEtr). Il a rejeté les prétentions en indemnité de X._ fondées sur les art. 429 al. 1 let. a et c CPP et a mis les frais de la procédure, d'un montant de 350 fr., à la charge de celui-ci. B. Par arrêt du 3 mars 2015, la Chambre pénale de recours de la Cour de justice a rejeté le recours de X._ contre le refus d'une indemnité pour tort moral. En tant que le recourant concluait également à ce qu'une indemnité pour ses frais de défense au sens de l'art. 429 al. 1 let. a CPP lui soit allouée et à ce que les frais de la procédure préliminaire ne soient pas mis à sa charge, la Chambre pénale de recours a refusé d'entrer en matière au motif que le recours ne contenait pas une motivation suffisante. C. X._ forme un recours en matière pénale au Tribunal fédéral contre cet arrêt. Il conclut à l'annulation de l'arrêt attaqué, au renvoi de la cause à la Chambre pénale de recours pour nouvelle décision, ainsi qu'au constat que la Chambre pénale de recours et le ministère public ont violé la présomption d'innocence. Il sollicite par ailleurs l'assistance judiciaire. D. Invités à se déterminer sur le recours, la cour cantonale et le ministère public ont conclu à la confirmation de l'arrêt entrepris.