Born in Tuy Viễn District (today's Tây Sơn District), Bình Định Province, he was a son of Trương Văn Hiến. Hiến was also the teacher of the Tây Sơn brothers (Nguyễn Nhạc, Nguyễn Lữ and Nguyễn Huệ), and encouraged them to revolt against Nguyễn lords.
Trương Văn Đa joined the Tây Sơn army while he was young and married a daughter of Nguyễn Nhạc. In 1783, Nguyễn Lữ and Nguyễn Huệ defeated the army of Châu Văn Tiếp and forced Nguyễn Ánh to flee to Pulo Condore. Under Trương Văn Đa, a navy launched an assault. As a result, Ánh had to flee to Phú Quốc, then to Siam. Nguyễn Huệ retreated from Cochinchina and left Đa in Gia Định (mordern Ho Chi Minh City).
In 1785, Siamese forces invaded Gia Định. Realizing they would be unable to beat the enemy, Đa retreated to Mang Thít and sent Đặng Văn Chân to Quy Nhơn for help. There, he joined the Battle of Rạch Gầm-Xoài Mút and defeated Siamese forces. In the next year, Nguyễn Lữ was granted the noble rank Đông Định vương ("King of Eastern Conquering") and given Gia Định as fief. Đa was later replaced by Phạm Văn Tham and called back to Quy Nhơn. Đa became the teacher of Crown Prince Nguyễn Văn Bảo. He retired after Nguyễn Nhạc's death.