Faits : A. A._ se trouve en détention provisoire puis pour des motifs de sûreté depuis le 29 juin 2012 au sein de la prison de Champ-Dollon, dans le cadre d'une procédure pénale dirigée contre lui notamment pour tentative d'assassinat. Par arrêt du 16 octobre 2015, la Chambre d'appel de la Cour de justice du canton de Genève l'a condamné à une peine privative de liberté de neuf ans, sous déduction de 1206 jours de détention avant jugement. Il n'a pas été tenu compte dans la fixation de la peine d'éventuelles conditions dégradantes de détention durant la détention avant jugement. Un recours contre cet arrêt est pendant devant la Cour de droit pénal du Tribunal fédéral. Le 22 juillet 2015, A._ a requis la constatation du caractère illicite des conditions de sa détention entre le 1 er mai 2013 et le 25 janvier 2015, soit 599 jours. Par ordonnance du 2 octobre 2015, le Tribunal des mesures de contrainte du canton de Genève (Tmc) a constaté que les conditions dans lesquelles s'était déroulée sa détention du 29 juin 2012 au 25 janvier 2015 avaient respecté les exigences légales, constitutionnelles et conventionnelles en la matière. Par arrêt du 1 er février 2016, la Chambre pénale de recours de la Cour de justice du canton de Genève (ci-après: la Cour de justice) a admis partiellement le recours de A._ contre l'ordonnance du 2 octobre 2015 et a constaté que sur une période de 190 nuits (entre le 1 er mai 2013 et le 25 janvier 2015) les conditions de détention n'avaient pas été conformes aux standards minimaux. B. Agissant par la voie du recours en matière pénale, A._ demande principalement au Tribunal fédéral d'annuler l'arrêt du 1 er février 2016 et de constater l'illicéité des conditions de détention pendant 599 jours. Il conclut subsidiairement au renvoi de la cause à l'instance précédente pour nouvelle décision au sens des considérants. Invité à se déterminer, le Ministère public du canton de Genève s'en remet à justice tant s'agissant de la recevabilité du recours que de ses conclusions. La Cour de justice a précisé avoir commis une erreur manifeste dans le décompte des jours de détention illicite et a corrigé le dispositif de son arrêt, en ce sens que les conditions de détention n'ont pas respecté les exigences légales sur une période de 226 nuits (et non pas de 190). Pour le reste, elle conclut au rejet du recours. Le recourant a répliqué par courrier du 1 er avril 2016.