Faits : A. A._, ressortissant du Monténégro, célibataire et sans domicile fixe, a été extradé le 19 février 2016 de Belgique sur la base d'un mandat d'arrêt international délivré par les autorités judiciaires genevoises. Le même jour, le Ministère public l'a mis en prévention du chef de brigandage en bande et par métier (art. 140 ch. 1 et 3 CP) pour avoir, le 12 août 2002, de concert avec un comparse, fait irruption dans une bijouterie à Genève, en criant qu'il s'agissait d'un hold-up et menaçant les vendeuses présentes avec un tournevis et un spray lacrymogène avant de briser des vitrines avec un marteau et d'emporter un lot de bijoux d'une valeur globale de 4'442'792 fr., étant précisé que le prévenu appartient à une bande organisée qui commet des brigandages dans toute l'Europe. Le prévenu a reconnu les faits reprochés. Son ADN ainsi que son empreinte digitale ont également été retrouvés sur des objets se trouvant dans un sac abandonné dans la bijouterie. Par ordonnance du 21 février 2016, le TMC, faisant droit à la demande du Ministère public, a ordonné la mise en détention provisoire de A._ jusqu'au 21 mai 2016 en raison de charges suffisantes ainsi que des dangers de fuite et de réitération. Entendu par la police judiciaire le 23 février 2016, le prévenu a reconnu son implication dans deux autres brigandages perpétrés à Genève le 15 janvier 2003 et le 21 avril 2004. Un mandat d'arrêt complémentaire a été établi afin d'étendre la poursuite en Suisse à ces faits. Selon les déclarations du recourant, il aurait été condamné en 1998 au Monténégro à une peine privative de liberté d'un an et demi pour tentative de meurtre, peine qu'il n'aurait pas encore exécutée. Il est en outre établi que le prévenu a été condamné: - en 2005 en Belgique à une peine de 8 ans de réclusion pour brigandage; - en 2006 en France à une peine de 9 ans de réclusion pour brigandage; - en 2009 en Allemagne à une peine de 7 ans de réclusion pour brigandage; - en 2012 en Belgique à une peine de 2 ans pour instigation à prise d'otage et à évasion. Le prévenu a été arrêté en France le 18 mai 2004; il a été détenu en France, en Allemagne et en Belgique. Il a exécuté les peines prononcées en Belgique ainsi que, vraisemblablement, en France. Par courrier du 6 avril 2016, adressé au Ministère public, le prévenu a sollicité le classement de la procédure et sa mise en liberté immédiate et sans conditions, aucune peine complémentaire ne pouvant, selon lui, lui être infligée (art. 8 al. 2 CPP et 49 al. 2 CP). B. Le 8 avril 2016, le Ministère public a refusé la mise en liberté du prévenu. En l'état de l'instruction, les différentes condamnations n'étaient pas encore toutes confirmées par les autorités des états concernés. Par ordonnance du 12 avril 2016, le Tribunal des mesures de contrainte de la République et canton de Genève a refusé la mise en liberté du prévenu. Par arrêt du 10 mai 2016, la Chambre pénale de recours de la Cour de justice de la République et canton de Genève a confirmé la mise en détention provisoire. C. Par acte du 26 mai 2016, A._ recourt contre cet arrêt auprès du Tribunal fédéral. Il conclut à l'annulation de l'arrêt cantonal, à sa mise en liberté immédiate et sans conditions, et se réserve le droit de réclamer une juste et équitable indemnité sur la base de l'art. 431 CPP. Subsidiairement, le recourant conclut à l'annulation de l'arrêt cantonal et au renvoi de la cause à la Cour de justice pour nouvelle décision dans le sens des considérants. Le recourant demande en outre à être mis au bénéfice de l'assistance judiciaire. La cour cantonale se réfère aux considérants de son arrêt. Le Ministère public se réfère à la décision entreprise et conclut au rejet du recours. Le recourant réplique et persiste dans ses conclusions.