Le DLEM a été créé le 1er avril 1976 par changement d'appellation du Détachement de Légion étrangère des Comores, lui même issu de la 2° Compagnie du 3° Régiment étranger d'infanterie. Implanté à Dzaoudzi, le DLEM a pris cette appellation après l'accession des Comores à l'indépendance en juillet 1975.
Au mois de novembre 1967, la 2° Compagnie du 3° REI quitte le camp de Sakaramy à Madagascar pour venir s'implanter dans l'archipel des Comores. La compagnie s'installe sur le rocher de Dzaoudzi dans les rares et vétustes bâtiments laissés à l'abandon par la gendarmerie comorienne. Les conditions de vie sont très difficiles car il n'y a pratiquement rien sur place depuis que le siège du gouvernement du territoire a été transféré à Moroni, sur l'île de La Grande Comore. Une section est envoyée à Voidjou en Grande Comore. Les sections restées à Dzaoudzi nomadisent à tour de rôle à Anjouan et Mohéli. En 1973, le 3° REI quitte définitivement Madagascar et rejoint la Guyane. La 2° Compagnie, quant à elle, reste aux Comores. Le 1er août 1973 elle devient une unité formant corps sous l'appellation de Détachement de Légion étrangère des Comores (DLEC).
Le PC du détachement, la section de commandement, trois sections de combat et un élément marine pour LCM se trouvent à Dzaoudzi. Une section de combat est au camp Voidjou. Une équipe de transit est détachée à La Réunion où le commandement des forces françaises du sud de l'océan Indien vient de s'installer après avoir quitté Madagascar. Garant de la présence française à l'entrée du canal de Mozambique, le DLEC a comme mission d'intervenir dans cette zone de l'océan Indien. La situation des Comores est très instable et certains politiciens comoriens prônent l'indépendance. Territoire d'outre-mer depuis 1946, l'archipel des Comores accède finalement à l'indépendance à la suite du référendum de 1975. Seule l'île de Mayotte veut rester française et un second référendum la conforte dans son choix avec plus de 95% de "oui" à la France. Mayotte prend le statut de collectivité territoriale. Les trois autre îles de l'archipel forment alors la République fédérale islamique des Comores. Le Détachement de Légion étrangère des Comores se transforme en Détachement de Légion étrangère de Mayotte et change de structures.
Le chef de corps du DLEM est le commandant militaire de Mayotte (COMIL). Il représente le général commandant supérieur des FAZSOI et a délégation de commandement sur l'ensemble des forces armées stationnées ou de passage à Mayotte. Il est également le correspondant militaire privilégié du préfet, représentant du gouvernement. Depuis 1984, le DLEM a la garde de l'étendard du 2° Régiment étranger de cavalerie.
