Faits : A. A.a. Par arrêt du 7 octobre 2014, la Chambre pénale d'appel et de révision de la Cour de justice du canton de Genève a ordonné que A._ soit soumis à un traitement institutionnel contre les addictions au sens de l'art. 60 CP, la peine privative de liberté de 4 ans et 6 mois, sous déduction de 489 jours de détention avant jugement, qui lui avait été infligée en première instance étant suspendue au profit de la mesure prononcée (art. 57 al. 2 CP). Dès le 25 novembre 2014, le Service d'application des peines et mesures (SAPEM) a placé A._ au sein de la fondation B._ à Lausanne. A.b. Par requête du 21 août 2015, le Ministère public, se fondant sur un rapport du SAPEM du 18 août 2015, a demandé au Tribunal d'application des peines et mesures (TAPEM) la levée de la mesure institutionnelle et la réincarcération immédiate de A._ afin qu'il purge le solde de peine. Par ordonnance du 25 août 2015, le TAPEM a nommé Me Daniel Kinzer à la défense d'office de A._. Ce dernier ne s'est pas présenté à l'audience du 1er septembre 2015 devant le TAPEM, qui a suspendu la procédure dans l'attente du traitement de la requête de récusation du Procureur déposée par A._, finalement rejetée par arrêt du 2 novembre 2015 de la Chambre pénale de recours de la Cour de justice. A.c. Le 2 septembre 2015, le SAPEM a émis un ordre d'écrou et demandé que A._ soit détenu à la prison de Champ-Dollon dès son arrestation dans l'attente de la décision du TAPEM. Par décision du même jour, le SAPEM a décidé de " la réintégration [de A._] en milieu pénitentiaire fermé dans l'attente de la décision du Tribunal d'application des peines et des mesures quant à la poursuite de la mesure au sens de l'art. 60 CP ". L'autorité a justifié sa décision par le non-respect par l'intéressé du cadre mis en place par les intervenants de la fondation B._, sa consommation régulière de produits stupéfiants, en particulier à l'intérieur de l'institution, ses fugues régulières et le fait qu'il n'était plus dans une démarche thérapeutique. Elle relevait également son défaut à l'audience du 1er septembre 2015 devant le TAPEM et que la fondation B._ était sans nouvelle de lui depuis sa fugue signalée le 31 août 2015. Cette décision a été notifiée à A._ le 14 janvier 2016. Dans l'intervalle, le 14 décembre 2015, l'intéressé avait été arrêté puis écroué à la prison de Champ-Dollon. A.d. Par jugement du 28 janvier 2016, le TAPEM a ordonné la levée de la mesure institutionnelle au sens de l'art. 60 CP et la réincarcération de A._ dans l'exécution du solde de sa peine. B. Par arrêt du 1er juillet 2016, la Chambre pénale de recours de la Cour de justice a déclaré irrecevable le recours de A._ dirigé contre la " décision de placement en milieu fermé (mesure conservatoire) " du SAPEM du 2 septembre 2015. En substance, elle a retenu que le recours n'avait pas été formé dans le délai et que A._ n'avait plus d'intérêt actuel à faire constater la nullité, éventuelle, de la décision du SAPEM. Par ailleurs, la Chambre pénale de recours a rejeté la demande d'assistance judiciaire formée par A._, considérant que son recours était dépourvu de chances de succès. C. A._ forme un recours en matière pénale auprès du Tribunal fédéral contre ce jugement. Il conclut, avec suite de frais et dépens, à ce qu'il soit ordonné à l'autorité intimée d'entrer en matière sur son recours contre la décision de placement en milieu fermé (mesure conservatoire) rendue par le SAPEM, et que l'assistance judiciaire pour la procédure cantonale de recours lui soit accordée. Il sollicite par ailleurs le bénéfice de l'assistance judiciaire. D. Invités à se déterminer, la Chambre pénale de recours s'est référée aux considérants de son arrêt, tandis que le SAPEM a présenté des observations et conclu au rejet du recours. Le recourant a renoncé à répliquer.