Cao Bang's proximity to China has meant that it has had a somewhat turbulent history, having changed hands a number of times. The Au Viet were a conglomeration of upland tribes living in what is today the mountainous region of northernmost Vietnam, western Guangdong, and southern Guangxi, China, since at least the 3rd century BC. Their capital was located in what is today Cao Bang Province of northeastern Vietnam. What are now the Vietnamese provinces of Cao Bang and Lang Son were known as chau Quang Nguyen during the time of the Ly and Tran Dynasties. Quang Nguyen became part of Dai Viet in 1039, when Emperor Ly Thai Tong expelled Nung Tri Cao, a Nung leader, from the area.
Cao Bang history can be traced to the Bronze Age when the Tay Au Kingdom flourished. They had shifted their capital to Co Loa in Red River Delta but the Vietnamese culture dominated. The Kings fortified their territory around the 10th century due to its proximity to the Chinese border. The feudal dynasties that ruled the area were Tay lords, Be Khac Thieu and Nga Dac Thai. In the 1430s, the Le Dynasty had many rebellions. Royalty faced strong revolt during the 16th and early part of 17th century – Mac Dang Dung initially occupied the territory and the Le throne in 1527. However, the Le kings were reinstated in 1592. Still, the war for control of the region continued and Mac family had the upper hand as they declared it an independent region and ruled for 75 years. As witness to this period, here lie ruins of a temple, which was also the palace of the Mac Kings. It can be seen in the town of Cao Binh, which is located about 12 kilometres (7.5 mi) north of the town of Cao Bang. Cao Binh was a prominent administrative town until the French occupied the territory; the capital was shifted to the Cao Bang peninsula when the French conquered the area in 1884. They fortified the town with a fort on a hill overlooking the town (ruins of this fort are seen even now). This fort area is now a high security zone of the People’s Army of Vietnam.
Cao Bang has a long history of revolutionaries and nationalists. The significant history of the peninsula to the present regime is recorded from the 1920s when it became the “cradle of the revolutionary movement in the north”. Many pro-independence groups based themselves in the mountains. The Communist Party of Vietnam chose the province as a base, using the rough terrain as protection. Its historicity was further accentuated when Ho Chi Minh, on his return from China in exile in 1941, made his headquarters at Pac Bo, in Truong Ha commune, Ha Quang district, 56 kilometres (35 mi) north of Cao Bang for the decisive revolutionary movement between 1940 and 1945.
In 1950, the province had 10 districts: Bao Lac, Ha Lang, Hoa An, Nguyen Binh, Phu Thach, Phuc Hoa, Quang Uyen, Thach An, Tran Bin and Trung Khanh. In 1958, Tran Bien was renamed Tra Linh. The district of Thong Nong was created out of part of the district of Ha Quang by Decision 67-CP on 7 April 1966. The districts of Phuc Hoa and Quang Uyen were merged to become Quang Hoa by Decision 27-CP on 8 March 1967. The district of Ha Lang was abolished and integrated into the districts of Quang Hoa and Trung Khanh by Decision 176-CP on 15 September 1969.
In December 1978, the two districts of Ngan Son and Cho Ra were transferred from the province of Bac Thai to Cao Bang by a decree of the congress of the Communist Party. This meant that Cao Bang had 11 districts: Bao Lac, Ha Quang, Hoa An, Nguyen Bình, Quang Hoa, Thach An, Thong Nong, Tra Linh, Trung Khanh, Ngan Son and Cho Ra. The district of Cho Ra was renamed Ba Be by Decision 144-HĐBT on 6 November 1984.
On 27 February 1979, during the Sino-Vietnamese War, Chinese infantry entered the city of Cao Bang and occupied it, inflicting a "scorched earth" policy by levelling most of the city, including places of worship. The historical areas near the Pac Bo caves in the commune of Truong Ha in Ha Quang district were mined and bombed, demolishing most of the cave mouth where Ho Chi Minh based his guerrilla activities in the 1940s and 1950s. In 1996, the districts of Ngan Son and Ba Be were transferred into the newly-created province of Bac Kan. The district of Bao Lam was created by carving out a portion of Bao Lac district, in accordance with Decree 52/2000/NĐ-CP on 25 September 2000.