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._.

Considérant en droit :
1.
Il résulte des conclusions prises par le recourant et de la motivation présentée que celui-ci a restreint son recours à la période de détention antérieure au jugement d'appel du 11 novembre 2013 clôturant la procédure de jugement au fond.
2.
Le recourant soutient avoir subi un traitement contraire à l'art. 3 CEDH pour sa détention avant jugement. Il invoque son droit d'obtenir un constat de l'illicéité des conditions de détention, lequel relève de la compétence du TAPEM pour la détention avant jugement, lorsque le jugement pénal est en force. Il se réfère à l'arrêt 6B_573/2015 du 17 juillet 2015 consid. 3.1 (publié aux <ref-ruling>).
Le TAPEM, en référence à l'art. 3 de la loi du 27 août 2009 d'application du code pénal suisse et d'autres lois fédérales en matière pénale (LaCP; RS/GE E 4 10), a indiqué être l'autorité compétente pour examiner les conditions de détention avant jugement. Il a toutefois nié un intérêt juridique du recourant à un tel examen, pour le motif que celui-ci y aurait prétendument renoncé en ne le réclamant pas durant la procédure pénale ayant abouti à l'arrêt du 11 novembre 2013. Il a ainsi déclaré la requête du recourant irrecevable. L'autorité précédente a quant à elle admis la compétence du TAPEM pour la détention avant jugement mais a renvoyé le recourant à agir devant le DSE, autorité compétente pour la détention postérieure au jugement en vertu de l'art. 5 al. 2 let. d LaCP.
L'approche du TAPEM selon laquelle le recourant aurait renoncé à invoquer l'art. 3 CEDH ne peut être suivie. Aucun élément ne permet de supposer que le recourant aurait contrevenu à la bonne foi en procédure. Il n'est par ailleurs pas en soi exclu d'obtenir un constat postérieurement au jugement de condamnation, même si les conditions de détention avant jugement doivent en principe être examinées dans le cadre dudit jugement. Tout en admettant la compétence du TAPEM, l'autorité précédente a toutefois donné la préférence à une compétence par attraction du DSE. Il n'est toutefois pas constaté que le DSE aurait été saisi à ce stade. L'autorité précédente ne lui a pas non plus transmis le dossier. On aboutit ainsi à une situation où la requête du recourant tendant au constat de l'illicéité des conditions de détention avant jugement n'est traitée par aucune autorité, alors même que le recourant a saisi le TAPEM, autorité en principe compétente. L'approche de l'autorité précédente constitue un déni de justice. Le recours doit être admis, l'arrêt attaqué annulé et la cause renvoyée à l'autorité précédente pour nouvelle décision.
3.
Le recourant, qui obtient gain de cause, ne supportera pas de frais. Le canton de Genève n'a pas non plus à en supporter (art. 66 al. 1 et 4 LTF). Le recourant a droit à des dépens à la charge du canton. Cela rend sans objet sa demande d'assistance judiciaire.

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis, l'arrêt attaqué est annulé et la cause est renvoyée à l'autorité cantonale pour nouvelle décision.
2.
Il n'est pas perçu de frais judiciaires.
3.
La République et canton de Genève versera au conseil du recourant une indemnité de 3'000 fr. à titre de dépens pour la procédure devant le Tribunal fédéral.
4.
Le présent arrêt est communiqué aux parties et à la Cour de justice de la République et canton de Genève, Chambre pénale de recours.
Lausanne, le 13 avril 2016
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
La Greffière : Cherpillod