蔡素玉本來係親北京商界政黨港進聯嘅成員，1995年首度參選立法局直選，挑戰當時港島東嘅現任議員李柱銘落敗。1996年，蔡素玉加入臨時立法會。2000年立法會選舉，蔡素玉為咗加入民建聯名單以便贏取立法會議席而參加民建聯，重夥拍程介南合組名單參選港島區，雖然選舉期間受程負面新聞影響，但仍成功當選。蔡素玉一度持有民建聯港進聯雙重會藉，而且同時係兩個政黨嘅常委，直到民建聯同港進聯合併。2005年，蔡素玉獲政府委任做太平紳士。
2004年香港立法會選舉，雖然事前唔被睇好，但係泛民主派配票失算，令佢最終可以些微票數壓倒何秀蘭奪得港島區最後一個議席。