Faits : A. En juin 2012, dans le cadre d'une procédure d'entraide requise par les autorités guatémaltèques, en relation avec des accusations dirigées contre X._ d'avoir procédé, alors qu'il travaillait pour le compte de la police nationale du Guatemala, à des « actes de nettoyage social », l'organisation A._ (A._) a versé à la procédure pénale un enregistrement vidéo de déclarations du dénommé B._. Celui-ci avait été détenu 15 ans durant au Guatemala. Il était incarcéré à la prison de xxx lors d'une intervention de la police et de l'armée, le 25 septembre 2006, au cours de laquelle sept détenus ont été tués. B._ décrivait cet événement et affirmait avoir assisté à l'assassinat de l'un de ces détenus par X._. Ce dernier, domicilié à U._, a été arrêté et mis en prévention d'assassinat, le 31 août 2012, pour des exécutions extrajudiciaires commises en 2005 (évadés de la prison « yyy ») et pour celles de la prison de xxx. B._ a été entendu en qualité de témoin par le Ministère public les 1er septembre et 14 décembre 2012. X._ et ses avocats ont déposé plainte, les 5 et 12 décembre 2012, contre B._ pour dénonciation calomnieuse et faux témoignage, visant les propos tenus le 1er septembre 2012. Par ordonnance du 21 décembre 2012 (confirmée sur recours), le Procureur général a ordonné la suspension de l'instruction de cette cause. Par jugement du 6 juin 2014, le Tribunal criminel du canton de Genève a reconnu X._ coupable d'assassinats et l'a condamné à la privation de liberté à vie. En bref, le tribunal, en se fondant notamment sur le témoignage de B._, a retenu que X._ était l'un des auteurs principaux des homicides volontaires commis sur sept détenus dans la prison de xxx; il avait agi en tant que coauteur sur six d'entre eux et comme auteur direct sur le septième. X._ a formé appel par déclaration du 29 septembre 2014. Le Ministère public a formé appel joint. Par avis du 20 novembre 2014, le Ministère public a repris la procédure ouverte contre B._ « vu le jugement rendu le 6 juin 2014 par le Tribunal criminel ». Par ordonnance du 24 novembre 2014, il a décidé de ne pas entrer en matière. B. Par arrêt du 2 février 2015, la Chambre pénale de recours de la Cour de justice genevoise a déclaré irrecevable le recours formé par X._ contre cette ordonnance de non-entrée en matière, frais à charge du recourant. C. X._ 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, à l'annulation de la décision querellée et au renvoi de la cause à l'autorité précédente afin qu'elle statue sur son recours et, à nouveau, sur les dépens de l'instance cantonale. Il requiert, en outre, le bénéfice de l'assistance judiciaire. Invités à formuler des observations, la cour cantonale y a renoncé, cependant que le Ministère public a conclu au rejet du recours, en se limitant à renvoyer aux considérants de l'arrêt du 2 février 2015. Cette détermination a été communiquée au recourant pour information.