It is not known when Cui was born, but it is known that his family was from Bei Prefecture (貝州, part of modern Xingtai, Hebei). His father Cui Yixuan (崔義玄) had served as a general and official under Tang's first three emperors -- Emperor Gaozu, Emperor Taizong, and Emperor Gaozong (Wu Zetian's husband) and had been created by Emperor Gaozu as the Duke of Qingqiu. When Wu Zetian was a favorite concubine of Emperor Gaozong, Cui was part of a court faction that supported her in her effort to displace Emperor Gaozong's first wife Empress Wang and later, after she did become empress, assisted in her effort to take vengeance on officials who opposed her ascension, including Emperor Gaozong's uncle Zhangsun Wuji. After Wu Zetian became "emperor" in 690, she remembered his contributions to her and further posthumously honored him.
After Cui Yixuan's death, Cui Shenji inherited his title. As of 692, he was serving as the minister of vassal affairs (司賓卿, Sibin Qing), when Wu Zetian gave him the designation of Tong Fengge Luantai Pingzhangshi (同鳳閣鸞臺平章事), making him a chancellor de facto. Just slightly over a month later, however, he, along with other chancellors Li Youdao, Wang Xuan, Yuan Zhihong, Li Yuansu, and other officials Kong Siyuan (孔思元), and Ren Linghui (任令輝), were falsely accused of crimes by Wu Zetian's secret police official Wang Hongyi. They were relieved from their posts and exiled to the Lingnan region. He was gradually repromoted. Later, during the reign of Emperor Gaozong's and Wu Zetian's son Emperor Zhongzong, he served as the chief judge of the supreme court (大理卿). It is not known when he died.