Grande admiratrice de Tariq Ramadan, Houria Bouteldja fonde en 2003 en compagnie d'autres personnes le collectif féministe les Blédardes, en réaction au collectif Ni putes ni soumises. Au sein du collectif "Une école pour tous et toutes", elle s'oppose à la loi sur les signes religieux à l'école, considérant l'interdiction du port du voile comme une pratique "néo-coloniale."

Porte-parole du Mouvement des Indigènes de la République, elle y poursuit son action contre ce qu’elle nomme le « continuum colonial » en compagnie des lieutenants de Tariq Ramadan et du Collectif des musulmans de France.

En 2008, le Mouvement des indigènes de la République commémorait le massacre de Sétif en défilant sous des pancartes rendant hommage au Cheikh Yassine et à Hassan Nasrallah (Hezbollah) avant de faire applaudir « les martyrs palestiniens ».

Elle se fait connaître du grand public français par sa dénonciation virulente de l'"islamophobie" : un mot qu'elle utilise pour confondre critique de l'Islam ou de l'intégrisme musulmans avec une forme de racisme anti-musulmans, ce qui permet de discréditer tout journaliste ou militant de la laïcité.

Invitée régulièrement dans l'émission de télévision "Ce soir (ou jamais !)", elle se distingue par ses prises de position en faveur de mouvements radicaux tels que le Hezbollah ou le Hamas, pour avoir qualifié Alain Finkielkraut de « sioniste ainsi que par l'utilisation du néologisme « souchien » (ou sous-chiens) pour désigner les « français de souche » qu'elle identifie aux « blancs », provoquant des polémiques sur la réduction des français de souche aux seuls blancs et une possible intention raciste dissimulée derrière un jeu de mots avec « sous-chiens ». L'hebdomadaire Marianne notamment réagira à cette déclaration dans un article intitulé « Une petite leçon de racisme », comparant ces propos aux écarts verbaux de Jean-Marie Le Pen 8. Houria Bouteldja réfute ces accusations estimant désigner « de façon humoristique d’hypothétiques Français de souche ».

Elle ajoute, dans la même émission du 21 juin 2007, que la nomination de Fadela Amara (présidente de l'association Ni putes ni soumises) au gouvernement Fillon est une "promotion à l'islamophobie et au racisme".