Searsia tomentosa is a much branched, evergreen shrub or small tree up to 6 m. Stem is smooth, greyish to dark brown, branchlets are reddish and hairy when young. The tree has glossy tri-foliate leaves, that are lanceolate-elliptic shaped, margins are entire or roughly toothed. Easily distinguished by its leaflets: the upper surface is dark green or greyish green and glabrous when mature, while it is creamy white and velvety to woolly below. In new apical growth, the leaves are red above. The midrib and margins are yellow or red, with pinnate veins.

Flowers are miniature, hairy, yellowish white, in dense terminal heads at the end of branches. A dioecious species, male and female flowers are borne on separate trees, the flowers emitting a strong unpleasant or offensive scent that attracts flies, in winter and spring (from July to October). The fruits are drupes (fleshy fruits with a hard seed inside), covered densely in hairs that are creamy-white or grey, borne in clusters at the stem-tip, in late winter, spring and summer (from June to February).