Op 9 juli 1940 had Rex haar zogeheten Formations de Combat (Strijdformaties) opgericht als partijmilitie onder leiding van de advocaat Joseph Pévenasse. Voor de jeugd bestond er de Jeunesses Rexiste (Rex-jeugd) onder het commando van provoost John Hagemans. De formatie, die onder leiding stond van de Vlaming[!] Rutger Simoens zal eind 1940 begin 1941 de eerste vormen van straatgeweld uitvoeren, ondermeer tegen locale besturen. In Wallonië en in Brussel was de rol van de paramilitaire milities in de eerste bezettingsjaren veel belangrijker dan in Vlaanderen. Er werd zelfs even door de Duitsers gevreesd voor een gewelddadige machtsgreep door Rex. Simoens werd later opgevolgd door Brahy.

De Formations de Combat telden in 1943 tussen de 600 en 850 leden. Uit de Formations de Combat ontstonden later de beruchte Brigades. Enkele maanden na het vertrek van het Waals Legioen naar het Oostfront, werd op 17 november 1941, naar het voorbeeld van de Vlaamse Fabriekswacht, de zogeheten Waalse Wacht of de Gardes Wallonnes (G.W.) opgericht die belast werden met de bewaking van strategische plaatsen zoals luchthavens, bruggen en spoorwegen. De Gardes Wallonnes (Waalse Wacht) telden in 1943 en 1944 ongeveer 1.500 leden.

Als antwoord op de verzetsdaden door de Partizanen was binnen Rex een nieuwe ster rijzende: Charles Lambinon, bijgenaamd 'onze Himmler' of 'de Waalse Himmler', een handelsreiziger van beroep. Charles Lambinon was in januari 1943 op eigen aandringen chef van het Département de Sécurité et d'Information (D.S.I.) geworden. Het D.S.I. was in het voorjaar van 1943 opgericht, met het doel om Rex-leden door te lichten en de tegenstanders van Rex te registreren, aan te houden en te vervolgen. Het werkte voor dat doel nauw samen met de Sicherheitspolizei-Sicherheitsdienst (Sipo-SD). Daarnaast was het de bedoeling dat het DSI bescherming zou bieden aan haar partijleden en sympathisanten tegen de aanslagen van het verzet. Het DSI zal pas echt actief worden wanneer Charles Lambinon er de chef van werd.

In verschillende Waalse steden ontstonden in de zomer van 1943 vanuit en door het DSI gecontroleerde terreurcellen van Rexistische origine, Brigades genoemd. Zo richtte Lambinon in Brussel de «Brigade Z» op, die hij onder het bevel plaatste van Jules Funken, een voormalig inspecteur van de Luikse gerechtelijke politie. In andere steden werden eveneens Brigades opgericht: Brigade A in La Louvière, Brigade B in Charleroi, Brigade C in Hoei, Brigade D in Luik en de Brigade F in Mons.

  De Brigade A uit La Louvière was ontstaan uit de locale politie die geleid werd door de Rexist Edgard Duquesne. Duquesne stond voordien al bekend als de leider van zijn beruchte privémilitie de zogenaamde Bande Duquesne die onder Lambinon officieel de naam Brigade A meekreeg. Toch zal deze Brigade de ganse oorlog berucht blijven als de Bande Duquesne en dat vooral omwille van haar gewelddadig optreden.

In Charleroi was de Rexist Henri Merlot het feitelijke hoofd van de Brigade B. Merlot was zowel oorlogsschepen als locale kringleider van Rex in Groot-Charleroi. Vanaf november 1943 werd de Brigade B gecommandeerd door de F. De Mayer uit Charleroi en zijn Brigade werd aldus de Waalse tegenhanger van de DeVlag terreurgroep rondom Robert Verbelen in Vlaanderen. De Brigade B telde in 1944 tussen de 300 en 500 leden. De Police Merlot (=Brigade B) evenals Bande Duquesne (=Brigade Z) opereerden nagenoeg autonoom van Rex en zorgden voor een sfeer van terreur en geweld in het bezette Wallonië. Het DSI werkte meer en meer onafhankelijk van REX en opereerde haast als een staat in een staat, net zoals dit ook het geval was met de Duitse SS.

De verhouding tussen de Sipo-SD en de «Brigade Z» bleek erg wankel. De Brigade Z bestond voornamelijk uit gewetenloze huurlingen, schurken en bandieten, die reeds voor het begin van WOII een lange lijst van criminele feiten meedroegen. Zo waren zij bijvoorbeeld gespecialiseerd in de opsporing en vervolging van welstellende joden, wat hen de mogelijkheid gaf tot scrupuleuze afperserijen. In augustus 1943 leidde een dergelijk incident er zelfs toe dat een aantal Brigadeleden door de Duitse Feldgendarmerie[!] werden gearresteerd.  Zowel de DSI van Lambinon en zijn Brigades stonden overal bekend als door en door corrupte en gewelddadige collaborateurs. Geweldpleging en elementaire foltering werden al gauw schering en inslag in de gevangeniscellen van het DSI-gebouw aan het Brusselse Rouppeplein. Een legioensoldaat die voor korte tijd werd overgeplaatst naar de Brigade Z stond versteld over het geweld waarvan hij dagelijks getuige was. Toen de Sipo-SD in juli naar het bureau aan het Rouppeplein werd geroepen om er een gewurgd lijk op te halen, verbood Abwehr-chef Canaris de Brigade Z nog langer ondervragingen uit te voeren.

Een andere rijzende ster die deze ontwikkeling voluit steunde was Louis Collard die in 1943 bliksemsnel carrière had gemaakt binnen REX. Hij werd dat jaar de belangrijkste en meest invloedrijke adviseur van interim-leider Victor Matthijs. Collard stond in voor de interne leiding van het departement en was verantwoordelijk voor alle externe organen en verzorgde tegelijk alle relaties met de Duitse Militärverwaltung. Na de oorlog zal Collard op zijn proces zijn rol binnen Rex minimaliseren, maar in werkelijkheid was het Collard die vanaf het najaar 1943 -meer dan wie ook- het beleid van REX bepaalde gedurende het laatste bezettingsjaar en was daarmee de onbetwiste derde man van Rex geworden, direct achter Victor Matthijs en SS-Obersturmbannführer Léon Degrelle.