Faits : A. X._ a été placé en détention à la prison de Champ-Dollon depuis le 11 septembre 2012. Il a été condamné par arrêt sur appel, définitif, du 11 novembre 2013 (le dossier cantonal ne permet de déterminer ni pour quelles infractions il a été sanctionné, ni quelle peine lui a été infligée). B. Le 13 mars 2015, X._ a déposé une requête auprès du Tribunal d'application des peines et des mesures (ci-après: TAPEM) du canton de Genève tendant au constat et à la réparation des conditions illicites dans lesquelles il dit avoir été détenu à la prison de Champ-Dollon. C. Par ordonnance du 19 juin 2015, le TAPEM a déclaré cette requête irrecevable. En substance, cette autorité a admis sa compétence pour examiner, une fois la condamnation définitive, les conditions de détention des détenus dans le cadre de la détention avant jugement, à l'exclusion de l'exécution de peine qui relève de la compétence du Département de la sécurité (ci-après: DSE). Elle a toutefois constaté que X._ ne s'était pas plaint de ses conditions de détention, alors même que son coprévenu l'avait fait, avant la fin de la procédure d'appel. X._ devait être considéré comme ayant, par son inaction et en pleine connaissance de cause, définitivement renoncé à soulever les griefs relatifs à ses conditions de détention jusqu'à l'entrée en force de l'arrêt de l'autorité d'appel. Le TAPEM a dès lors jugé la requête tardive et refusé d'entrer en matière sur celle-ci. Cette autorité a estimé pour le surplus n'être pas compétente pour examiner les conditions de détention de X._ lors de la phase d'exécution de la peineet renvoyé ce dernier à agir devant le DSE afin d'obtenir un constat relatif à l'illicéité de ses conditions de détention dès le 11 novembre 2013. D. Par arrêt du 25 août 2015, la Chambre pénale de recours de la Cour de justice de la République et canton de Genève a rejeté le recours formé par X._ contre cette ordonnance. S'agissant de la période avant jugement, la Chambre pénale de recours a considéré que X._ ne pouvait plus espérer obtenir de modification des conditions de sa détention avant jugement, puisque celle-ci avait pris fin avant que ne soit saisi le TAPEM. Cette autorité avait par ailleurs instruit les conditions de détention pour cette période, de sorte que les preuves à ce sujet étaient déjà recueillies. Dès lors X._ n'avait pas d'intérêt juridiquement protégé à ce qu'il incombe au TAPEM, plutôt qu'à une autre autorité, de compléter si nécessaire l'instruction dans le sens de ses observations du 14 avril 2015 quant à ses conditions de détention avant et après le terme de la procédure au fond, de constater formellement, s'il y avait lieu, l'illicéité de ses conditions de détention avant jugement. La Chambre pénale de recours a considéré que X._ pourrait faire valoir ses droits en saisissant le DSE ou en ouvrant action en responsabilité de l'Etat pour l'ensemble de la période passée à Champ-Dollon, le DSE étant compétent pour la période postérieure au jugement. Renvoyer X._ à agir pour l'entier de ses prétentions devant le DSE pour toute la période litigieuse répondait en outre à la crainte de césure exprimée par X._. Un renvoi au TAPEM ne se justifiait donc pas et le recours devait être rejeté. E. X._ forme un recours en matière pénale auprès du Tribunal fédéral contre l'arrêt du 25 août 2015. Il conclut, avec suite de frais et dépens, à son annulation et au renvoi de la cause à l'autorité cantonale afin qu'elle entre en matière sur sa requête tendant à ce qu'il soit statué sur l'illicéité de ses conditions de détention avant jugement et fait droit aux réquisitions de preuves sollicitées dans ses observations du 14 avril 2015. A titre subsidiaire, il sollicite l'annulation de l'arrêt et le renvoi de la cause à l'autorité cantonale pour nouvelle décision. Il requiert le bénéfice de l'assistance judiciaire. Invités à se déterminer, l'autorité précédente n'a pas répondu, le ministère public a conclu à la confirmation de l'arrêt attaqué. Ces observations ont été transmises à X._.