In 704, when Cui was still serving as deputy minister of civil service affairs, he was given the designation Tong Fengge Luantai Pingzhangshi (同鳳閣鸞臺平章事), making him a chancellor de facto. By late that year, when Wu Zetian was ill and was often attended only by her lovers Zhang Yizhi and Zhang Changzong, Cui made the suggestion to her that she should have her sons Li Xian the Crown Prince and Li Dan the Prince of Xiang attend to her -- not members of other clans (i.e., not the Zhang brothers). Wu Zetian, while thanking him for his input, paid no heed. Cui later supported the imperial censor Song Jing in Song's attempt to investigate Zhang Changzong for corruption and plotting treason, but Wu Zetian did not permit the investigation. She did, however, approve a petition jointly submitted by him and Li Jiao and supported by Huan Yanfan that the people who were found guilty and executed due to accusations by her secret police officials (such as Zhou Xing and Lai Junchen) early in her reign be posthumously restored to honor.
In spring 705, with Wu Zetian continuing to be ill, Cui entered into a plot with a number of officials and generals, including Zhang Jianzhi, Huan, Jing Hui, and Yuan Shuji, to kill the Zhang brothers. With agreement from Li Xian, they acted on February 20, killing Zhang Yizhi and Zhang Changzong, and then surrounding Wu Zetian. While they allowed her to retain the title of "emperor," they had her put under house arrest at the secondary palace Shangyang Palace (上陽宮) and forced her to yield the throne to Li Xian, who was formerly emperor, and he was restored to the throne (as Emperor Zhongzong). As she confronted the plotters, she said to Cui, "All of the others became key officials because of others' recommendations. Only you were personally selected by myself, and yet you stand here with them." Cui responded, "What I do today is to repay your Imperial Majesty's great grace to me."
In spring 706, with all five of the coup leaders already out of the capital, Wu Sansi and Empress Wei made accusations against them, and they were demoted to more remote prefectures -- in Cui's case, to be the prefect of Jun Prefecture (均州, roughly modern Shiyan, Hubei). Wu Sansi then had his strategist Zheng Yin further accuse the five of them of having participated in the plot of Emperor Zhongzong's son-in-law Wang Tongjiao (王同皎) -- who was executed early in 706 after having been accused of plotting to kill Wu Sansi and deposing Empress Wei. The five were further demoted with the provisions that they would never be allowed to return to the capital Chang'an, with Cui becoming the military advisor to the prefect of Bai Prefecture (白州, roughly modern Yulin, Guangxi). Wu Sansi then had accusations that Empress Wei was having affairs posted publicly in the eastern capital Luoyang, with the intent of incensing Emperor Zhongzong -- and then accused the five coup leaders of being behind this public humiliation. He then had his associates propose that the five be killed. Emperor Zhongzong, citing that the five had been previously awarded iron certificates that guaranteed that they would not be executed in recognition of their contribution, ordered that they be reduced to commoner rank and permanently exiled to the Lingnan region with their families -- in Cui's case, to Gu Prefecture (古州, roughly modern Lang Son Province, Vietnam). At the suggestion of Cui Shi, Wu Sansi then sent the censor Zhou Lizhen (周利貞) to the Lingnan region under guise of reviewing the affairs of the region but with instructions to kill the five. By the time that Zhou reached the region, though, Cui Xuanwei had already died. After Emperor Zhongzong's death in 710 and Li Dan, himself a former emperor, was restored (as Emperor Ruizong), Cui and his colleagues were posthumously honored, and his son Cui Qu (崔璩) received the title of Duke of Boling.
