Nguyễn Hữu An was born in the Truong Yen Commune of the Hoa Lư, Ninh Bình, Tonkin protectorate (Northern Vietnam).

In the Battle of Dien Bien Phu, he commanded 174th Regiment of the 316th Division,[1]: 270  and three times attacked Hill A1 (Éliane 2).

[1]: 271  2nd Corps, under his command, successively captured Quảng Trị and Huế; and in combination with armed forces of Military Region No.5 defeated nearly 100,000 regular troops of the ARVN within just 3 days at Da Nang.

He then commanded the entire corps to march along nearly 1000 km to engage in the Ho Chi Minh Campaign after having destroyed the ARVN defensive line in Phan Rang.

He held key posts in military such as Assistant Inspector General of the Vietnam People's Army, Deputy Chief concurrently Chief of Staff and Acting Commander of Military Region No.2 (1984–1987), Director of Army Academy (1988–1991), and Director of Academy of National Defense (1991–1995).