Wang Shenzhi was born in 862, during the reign of Emperor Yizong. His fifth-generation ancestor Wang Ye (王曄) served as the magistrate of Gushi County (固始, in modern Xinyang, Henan), and because the people loved him, he settled his family in Gushi. The family subsequently became known for their family business. His father's name was Wang Nin (王恁), and his mother was a Lady Dong. He had two older brothers, Wang Chao and Wang Shengui (王審邽).
In 881, the bandit leader Wang Xu, along with his brother-in-law Liu Xingquan (劉行全), captured Guang Prefecture (光州, in modern Xinyang); he was subsequently commissioned the prefect of Guang Prefecture by Qin Zongquan the military governor (Jiedushi) of Fengguo Circuit (奉國, headquartered in modern Zhumadian, Henan). Wang Xu forced the men of Guang Prefecture to join his army, and he made Wang Chao, who had previously been a government worker at the Gushi County government, his discipline officer. Later on, however, Qin turned against the Tang imperial government and was on the cusp of claiming imperial title himself. He ordered Wang Xu to pay taxes to him. When Wang Xu was unable to do so, he launched an army to attack Wang. Wang Xu, in fear, gathered 5,000 soldiers from Guang and Shou Prefectures and forced the people to cross the Yangtze River to the south. By spring 885, Wang had continued south and captured Ting (汀洲, in modern Longyan, Fujian) and Zhang (漳州, in modern Zhangzhou, Fujian) Prefectures, but was not able to hold either for long. By the time that Wang Xu reached Zhang Prefecture, his army was running low on food. As the terrain in Fujian Circuit (福建, headquartered in modern Fuzhou, Fujian), which Zhang Prefecture belonged to, was rugged, he ordered that the old and the weak be abandoned. However, in violation of his order, Wang Chao and his brothers continued to take their mother Lady Dong with them. Wang Xu rebuked them and threatened to put Lady Dong to death. They begged for Lady Dong's life, offering to die in her stead. Other officers also spoke on their behalf, and Wang Xu relented.
Meanwhile, by this point, Wang Xu had also become extremely paranoid, as he had been warned by a sorcerer that there was qi belonging to a king in his army, so he began to put to death anyone whom he considered to have talents surpassing his own—going as far as putting Liu Xingquan to death. The fact that Wang was willing to put someone as close to him as Liu to death terrified the other officers. When the army reached Na'an (南安, in modern Quanzhou, Fujian), Wang Chao persuaded Wang Xu's forward commander, who feared that he would be Wang Xu's next target, into turning against Wang Xu. The forward commander and Wang Chao thus laid an ambush for Wang Xu and, when he was caught off-guard, arrested him. Wang Chao initially wanted to support the forward commander to be the new leader, but the forward commander pointed out that it was Wang Chao's idea that allowed them to survive Wang Xu's cruelty, and so the army agreed to have Wang Chao become their leader. Wang Chao subsequently took over Quan Prefecture (泉州, in modern Quanzhou, Fujian) and obtained a commission from Chen Yan the governor (觀察使, Guanchashi) of Fujian Circuit (福建, headquartered in modern Fuzhou, Fujian) as the prefect of Quan Prefecture.
In 891, Chen Yan grew deathly ill. Chen sent an order to Wang Chao, summoning him to the circuit capital Fu Prefecture (福州), intending to entrust the matters of the circuit to him. Before he could depart, however, Chen died, and Chen's brother-in-law Fan Hui (范暉) got the soldiers at Fu Prefecture to support him as acting governor to resist Wang. Fan, however, soon lost the support of the soldiers, and Wang Chao sent his cousin Wang Yanfu (王彥復) and Wang Shenzhi as Wang Yanfu's deputy to lead an army to attack Fu Prefecture. However, they could not capture it quickly, and Fan sought aid from Dong Chang the military governor of Weisheng Circuit (威勝, headquartered in modern Shaoxing, Zhejiang), who dispatched an army to aid him. Hearing that news, Wang Yanfu and Wang Shengui submitted a report to Wang Chao, requesting to withdraw. Wang Chao refused. When they requested that he come to the front to oversee the attack, he responded:
If soldiers die, I will replace the soldiers. If the generals die, I will replace the generals. If the soldiers and the generals all are dead, I will go myself.
Wang Yanfu and Wang Shenzhi, fearful of the rebuke, intensified their attacks. By summer 893, the food supply in Fu Prefecture ran out. Fan abandoned it and fled, and the Weisheng army, still on the way, hearing that Fan had fled, returned to Weisheng. Fan was killed by his soldiers in flight. Wang entered Fu Prefecture and claimed the title of acting governor. After Wang Chao was subsequently made governor of Fujian, and then the military governor (with the circuit's name upgraded from Fujian to Weiwu (威武)), Wang Shenzhi served as deputy military governor. It was said that whenever Wang Shenzhi had faults, Wang Chao would batter him, but Wang Shenzhi would not complain. In 897, when Wang Chao grew ill, he did not try to pass his authorities to any of his sons; rather, he entrusted the matters of the circuit to Wang Shenzhi. After Wang Chao died around the new year 898, Wang Shenzhi offered the authorities to Wang Shengui, who was then the prefect of Quan Prefecture, but Wang Shengui declined on the account that he considered Wang Shenzhi more accomplished. Wang Shenzhi thus claimed the title of acting military governor of Weiwu and submitted a report of what occurred to then-ruling Emperor Zhaozong, who commissioned him as acting military governor and later in the year made him full military governor.
In 900, Emperor Zhaozong bestowed the honorary chancellor designation of Tong Zhongshu Menxia Pingzhangshi (同中書門下平章事) on Wang Shenzhi. He was later successively given the honorary titles of acting Sikong (司空) and acting Situ (司徒) (two of the Three Excellencies). In 902, Wang built an outer wall for Fu Prefecture. In 904, Emperor Zhaozong created him the Prince of Langye.