Nuxia floribunda is a small to medium-sized tree, usually 3 m to 10 m tall, although heights of up to 25 m may be attained. The main stem is often somewhat contorted and up to 600 mm in diameter. The fissured bark is rough and flaking and is grey to brown in colour. A lovely dense and rounded crown is often evident, contributing greatly to the visual appeal of the species.

The branchlets are angular and purplish, becoming paler with age. They may be smooth or finely hairy and prominent leaf scars are usually evident along their length. The leaves are simple, 40-160 x 10-70 mm, oblong to elliptic in shape, and taper to a pointed apex.

They may be opposite but more often are 3-whorled and this, together with the distinctive red to purple midrib visible on immature leaves, represents a valuable identification feature of the tree. The leaf margins are entire or faintly toothed and are often clearly undulating. The slender leaf stalks vary from 15 to 45 mm in length.

The sweetly scented, cream-white flowers are small in size, around 3 mm long, and are borne in large, branched inflorescences (cymose panicles) produced terminally and in the axils of leaves nearer the ends of the branches. Bracts are around 1 mm in length and both the calyx and corolla are 4-lobed, the stamens protruding. Flowering has been recorded from autumn to spring, mostly between the months of May and September.

The fruit is an ovoid capsule that protrudes slightly from the persistent calyx and splits into 4 lobes, revealing numerous tiny seeds. N. floribunda can be readily distinguished from other members of the genus by its large, striking inflorescences.