Cola greenwayi is a small to medium-sized perennial, evergreen tree of 3-25m high. Stem bark is grey-brown or dark brown, rough, flaking with young branches russet to light cinnamon brown or tomentose (densely covered with short, soft, felted hairs) at first, mixed with stellate or bunched hairs which fall readily.

Stipules are subulate-lanceolate to linear, 3-6mm long, dark to light brown or grey tomentose, and fall off early. Leaves simple, alternate, elliptic to oblanceolate, up to 270×75mm, glabrous at maturity, dark green above, paler green below, drooping, tapering at apex and base, margins entire, petiole up to 10-65mm long, with tomentose apical swelling below leaf base (pulvinus).

Inflorescences are one-flowered, axillary, solitary or fascicled and crowded on branchelets between the leaves. Flowers are unisexual, rarely bisexual, about 5×12mm, coloured by dark rusty brown, dense hairs, in leaf axial, in tight clusters along woody stems. Floral pedicels are jointed near the base, arising from sessile imbricating bracts which are 1.5-3.5mm long, without petals, sepals covered with rusty hairs, pedicels 7-20mm long, densely stellate-purbescent, hairs dark to light brown short or long, calyx 4-6-lobed almost to the base at flowering time, dorsally stellate-pubescent (with star-shaped hairs). Male flowers with staminal tubes about 2.5-4.5mm long, densely pubescent to subglabrous, anthers up to 8 in one row, sessile in a ring around the apex of stamina tube.

Female flowers with sessile ovary, densely stellate-pubescent, about 2 or 3mm wide, with a ring of rudimentary stamens around base, carpels 4-5 or less by abortion, orange yellow to deep orange. Flowering time is from October to January.

Fruit consist of 3-5 carpels, each about 20mm wide, joined in a ring, covered with dense short, soft, rusty-red hairs when young, yellow when ripe. Fruits ripen from November to May.