Protea madiensis was first described as a new species in a 1875 publication by the Linnean Society of London (read before the society in 1871) by Daniel Oliver, who described the new taxon from a specimen brought forth from the Speke and Grant expedition to find the source of the Nile. This specimen was collected by James Augustus Grant in December, 1862, when the trees were in full bloom, at a place called 'Madi' (see Madi people), hence the specific epithet ('from Madi'). Grant states in his notes that he encountered it for the first time here.^[2][6]

The synonym Protea bequaertii was described from the Belgian Congo.

In the first half of the 20th century botanists believed that there were four different Protea species occurring contemptuously together with each other in West Africa: P. argyrophaea, P. elliottii, P. madiensis and P. occidentalis. P. argyrophaea was the name for a smallish, shrubby plant, with silvery-white bracts subtending the inflorescence as opposed to pinkish as ascribed to P. madiensis by Hutchinson and Dalziel at the time (1954).^[3] In 1963 John Stanley Beard synonymised the first three taxa under the oldest name, P. madiensis.^[7]

At present, Protea madiensis has two accepted subspecies, the nominate eastern form, and the western form, subspecies occidentalis.^[3][8] It is impossible to distinguish the two taxa from each other using vegetative characteristics; instead, the two taxa can be distinguished by two details of the floral parts.^[7]

• P. madiensis subsp. madiensis Oliv. - This subspecies was originally said to occur from Senegal to Ethiopia in the north, to Angola, Malawi, Mozambique and Zambia in the south.^[3][7][8] The trees found growing in southern Nigeria are also seen as belonging to the nominate form.^[3][8] It is very variable over its range in leaf form and shape.^[3][7]
• P. madiensis subsp. occidentalis (Beard) Chisumpa & Brummitt - This taxon was originally described as found growing in the area from Guinea to Mali in the north, south to Sierra Leone, Benin and Cameroon.^[4][7] It is sympatric with the nominate form throughout its range. According to Beard in his original 1963 description of the taxon as P. occidentalis, a species independent of P. madiensis, it primarily differs from the nominate form in that the corolla, including outer lobes, is shorter, less than 1.5cm, and the floral tube, into which form the Protea flower has evolved, is glabrous or ciliated, as opposed to entirely pubescent.^[7]

This is one of the four most common Protea species in tropical Africa.^[9]