La loi-cadre qui changeait le statut des territoires de la France d’outre-mer est votée le 23 juin 1956.C’est en vertu de cette loi que l’adoption de nouvelles constitutions pour le Sénégal et la fédération du Mali devenait nécessaire. Après avoir consulté le projet de constitution du Sénégal, Serigne Cheikh s’est rendu compte que l’avenir de l’islam était dangereusement menacé. Ainsi avait-il estimé qu’un référendum était nécessaire pour l’adoption de la nouvelle constitution ; une idée qu’il partageait d’ailleurs avec les chefs religieux regroupés au sein du « Conseil Supérieur des Chefs religieux ». La position de Serigne Cheikh était d’autant plus justifiée qu’il était contre le projet d’une fédération du Mali qu’il trouvait sans avenir. Malheureusement, les autorités de l’époque ne l’entendaient de cette oreille en préférant la validation par l’Assemblée législative. Les nouvelles constitutions, fédérales et Sénégalaises furent ainsi promulguées les 22 et 24 janvier 1959.Le ministre de l’Intérieur de l’époque Waldiodo Ndiaye reconnaissait le problème de légitimité, mais invitait le peuple à saisir l’occasion des prochaines élections législatives pour sanctionner positivement ou négativement le gouvernement. C’est ainsi que Serigne Cheikh qui trouvait inefficace la stratégie du Conseil Supérieur des Chefs religieux, décida avec son parti, le PSS (Parti de la Solidarité sénégalaise) de participer aux joutes électorales du 22 mars 1959. Très au fait de la situation, il savait que ses adversaires politiques allaient inexorablement se ruer vers les autres chefs religieux pour solliciter leur suffrage… C’est tout ce qu’il souhaitait, car cela renforcerait le pouvoir de ces religieux que Mamadou Dia et ses alliés considéraient comme des féodaux.
Un de ses aînés marabouts le taquinait un jour, en lui disant « Même à Thiès, nous allons te battre », Al-Maktoum (L’énigmatique) de lui répondre : « Vous avez le droit de gagner, laissez-moi le devoir de perdre »… Devant la perplexité du patriarche, Serigne Cheikh lui dire « Vous comprendrez peut-être dans dix ou vingt ans ».Trois partis furent en lice à l’occasion de ces législatives : L’UPS, le PRA-Sénégal (Parti du Regroupement Africain) et le PSS. Selon les résultats officiels, l’UPS remporte les élections avec 83 % des suffrages exprimés, le PSS, 12,1 %, et le PRA, 4,9 %.Il va sans dire que le système électoral de 1959, n’était pas le même que celui de nos jours. Il existait de sérieux problèmes de transparence, et les élections étaient fortement entachées d’irrégularités. Serigne dénonça « Meurtres, incendies volontaires, coups et blessures, violences et voies de fait, arrestations arbitraires, séquestration de militants, etc. »Mais, notre démocratie étant encore trop jeune de tels manquements étaient tout-à-fait prévisibles.