Fu Sheng was overthrown and subsequently executed during a coup orchestrated by Fu Jian and his brother Fu Fa later that year. Deng Qiang would continue to serve the state following the regime change with Fu Jian as the new ruler. Also that same year, the Bingzhou warlord, Zhang Ping broke his allegiance to Former Qin and attempted to claim independence. In 358, Fu Jian led his troops to Fen River with Deng Qiang as his vanguard general. Zhang Ping sent out his adopted son, Zhang Ci, to battle the Qin forces. Deng Qiang and Zhang Ci fought for ten days, with neither side getting the upper hand. When Fu Jian moved to Tongbi (銅壁, in modern-day Tongchuan, Shaanxi), Zhang Ci charged into the Qin lines numerous times. In his last charge, he was struck by a spear from the Qin general Lü Guang, and Deng Qiang quickly subdued and brought him before Fu Jian. Zhang Ci's capture caused morale in Zhang Ping's army to collapse, so Ping quickly surrendered back to Qin.[8]
In 359, Deng Qiang campaigned against the rebel Gao Li (高離) in Lüeyang and vanquished him.[9] Later, he was appointed as Middle Assistant to the Imperial Secretary and worked close with Fu Jian's advisor Wang Meng. The two worked very well with each other and within a matter of weeks, they purged the government of corrupted officials and nobles while solving mismanaged law cases. Fu Jian was very pleased with this and exclaimed, "Now I know what a land ruled by law is like!"[10]
In an unspecified year, Zhang Wang (張罔), a member of the Chuge people, rebelled after gathering thousands of people as well as declaring himself the Grand Chanyu. As Zhang invaded and plundered numerous counties and commanderies, Deng Qiang was reappointed as General Who Establishes Fortitude, and with 7,000 soldiers, he managed to quell Zhang's rebellion. In 365, the chieftains, Cao Gu and Liu Weichen rebelled against Qin. While Fu Jian led the army against Cao Gu, Deng Qiang fought and captured Weichen at Mount Mugen (木根山; north of present-day Yulin, Shaanxi) in Shuofang. Peace was restored after the chieftains agreed to submit back to Qin.[11] In 366, Deng Qiang also participated in Wang Meng's campaign against the Longxi warlord, Li Yan, and was awarded the offices of General Who Establishes Martial Might and Inspector of Luozhou for his contributions.[12]
In 368, a major rebellion broke out led by Fu Jian's cousins, Fu Liu (苻柳), Fu Sou (苻廋) and Fu Wu (苻武), and his brother, Fu Shuang (苻雙). Deng Qiang and Wang Meng were tasked in defeating Fu Liu, who had made Puban (蒲阪, in modern-day Yuncheng, Shanxi) his base. Fu Liu left his son Fu Liang (苻良) to guard the city while he marched towards Chang'an to capture it. Deng Qiang caught him by surprise with a night raid, forcing him to retreat. Wang Meng then intercepted his retreat, leaving Fu Liu with only a few hundred men back to his base.[13] Wang Meng and Deng Qiang easily captured Puban and executed Fu Liu before joining Zhang Ci and Yang An in their assault against Fu Sou at Shancheng (陝城, in modern Sanmenxia, Henan). After all four rebels had been defeated, Deng Qiang was appointed General Who Establishes Valor and Inspector of Luozhou (洛州, covered parts of modern-day Henan and Shanxi).
The following year, the Jin dynasty Grand Marshal, Huan Wen, led his troops to conquer Former Yan. At the advice of Wang Meng, Fu Jian decided to support Yan to prevent Jin from gaining significant land in the north. Fu Jian sent Deng Qiang and Gou Chi (苟池) to Shancheng to reinforce Yan and oversee the upcoming battle between the two sides.[14] Yan managed to repel Jin thanks to the efforts of Murong Chui at the Battle of Fangtou but must now deal with Qin's demands. Yan had initially promised to Qin that they would surrender Hulao to them but retracted their statement, giving Fu Jian a pretext to invade them. Fu Jian had Deng Qiang, Wang Meng and Liang Chen (梁琛) capture Luoyang, which fell the following year. Shortly after, Deng defeated Murong Zang (慕容臧) at Xingyang.
An altercation nearly broke between Deng Qiang and Wang Meng during the war. Wang Meng intended to execute the general Xu Cheng (徐成) for returning late from scouting. Deng Qiang, who came from the same commandery as Xu, defended him, stating that Qin needs to preserve its numbers, even more so since Xu Cheng is a high-ranking officer. Wang Meng argued in favor of upholding military laws but Deng Qiang further advocated that Xu Cheng be redeemed by fighting the Yan forces in the upcoming battle. Even then, Wang Meng refused, causing Deng Qiang to rally his men against Wang Meng. Wang was impressed by Deng's dedication to protect Xu Cheng and finally pardoned him. Deng Qiang also apologised and the two reconciled.[15]
As Wang Meng and Murong Ping's armies came face to face at the Battle of Luchuan (潞川, in modern-day Changzhi, Shanxi), Wang Meng placed his trust in Deng Qiang to rout them despite Qin's inferior numbers. However, another disagreement occurred between the two. Deng Qiang wanted Wang Meng to appoint him Colonel-Director of Retainers after he wins, but Wang Meng pointed out that he did not have the power to do so, although he tried to compensate him with Administrator of Anding and a Marquis of ten thousand households. Deng Qiang withdrew unsatisfied and when the battle began, he was still asleep in his camp. Wang Meng quickly rode to his tent and made a compromise with Deng. When all was settled, Deng Qiang drank heavily before setting out with Zhang Ci and Xu Cheng. He personally charged into the enemy lines several times and killed several of the Yan troops. By noon, the Yan forces were annihilated and Murong Ping fled alone to Yecheng.[16]
Deng Qiang's last merit in the war would be at Xindu, where he defeated Murong Huan (慕容桓). After Qin conquered Yan, he was rewarded by Fu Jian with Credential Bearer, General Who Conquers The Caitiffs, Administrator of Anding and Marquis of Zhending Commandery (真定, in modern-day Shijiazhuang, Hebei). In 371, Wang Meng decided to honour his promise at Lu River and asked Fu Jian to make Deng Qiang Director of Retainers. However, Fu Jian believed that Deng Qiang deserves better for his past merits as well, and made him General Who Guards the Army and honored him as Specially Advanced.[17]
In 373, Former Qin conquered the region of Yizhou and Liangzhou from the Jin dynasty. However, one year later, two natives, Zhang Yu and Yang Guang (楊光), rebelled and tried to set up their state with the aid of Jin. Fu Jian dispatched Deng Qiang to destroy them while Jin sent Zhu Yao (竺瑤) and Huan Shiqian, who defeated Yao Chang and forced him to retreat to Wucheng (五城, around present-day Guanghan, Sichuan). Zhang Yu declared himself King of Shu and besieged Chengdu. However, Zhang Yu began to quarrel with his peers and followers and they all started fighting one another. With the rebels disunified, Deng Qiang and Yang An quickly routed them, causing Zhang Yu and Yang Guang to pull out to Mianzhu. Deng proceeded to defeat Zhu Yao and Huan Shiqian in the west before finally claiming Zhang Yu and Yang Guang's heads at Mianzhu. Before he left, Deng Qiang carved a stele at the Min Mountains.[18]
Fu Jian had long appreciated Deng Qiang but his recent victory in Yizhou impressed him very much. After Deng Qiang returned from Chengdu, Fu Jian summoned him to the palace, where he told him, "Long ago, your ancestor Zhonghua (Deng Yu) met with Han Shizu (Emperor Guangwu of Han). Now, you too have met me. How fortunate of the Deng clan." Deng Qiang replied, "I've always told myself that it was Guangwu who met Zhonghua, not Zhonghua who met Guangwu." Fu Jian laughed and said to him, "If it is as you say, then it is not you who's fortunate, but me for meeting such a worthy man."[19]
In 376, Deng Qiang, Zhang Ci and others led 200,000 infantry and cavalry troops to accompany the Grand Commander of the Northern Expedition, Fu Luo, in his conquest of the Dai state. After the fall of Dai, he was awarded the office of Inspector of Bingzhou. His final appearance in history would be in 378 during Fu Jian's grand siege of Xiangyang, serving as the vanguard general in attacking Fancheng with Yang An.[20] Details of his merits in the siege are not known, and his name ceases to appear in records from this point on. It could be inferred that Deng Qiang died sometime during the campaign, as Zhang Ci succeeded him in his office of Inspector of Bingzhou in c.March 379.[21]