Coccinia rehmannii is a slender perennial, creeper or climber, arising from a large tuberous rootstock, almost glabrous to rather densely hairy, becoming smooth whitish and speckled at maturity, especially in drier areas. The simple tendrils enable the vine to grow over and smother vegetation, cover fences and power lines, trees, shrubs and walls. It can grow up to 4 m high. The plant has perennial roots, woody at the base producing hypocotyl (carrot-like) tubers, that grow up to 0.5 m deep.

The leaves of C. rehmanni are simple, alternate, and paired, with a tendril on each node, except for the first nodes. The leaves are 20–80 × 25–130 mm, usually distinctly petiolate. Young leaves tend to be shallowly lobed. Upper leaf surface more or less densely white, pustulate. Lower leaf surface glabrous, sometimes wart-like; the leaf margin usually beset conspicuously with small teeth and often bears trichomes.

Flowers are whitish cream-coloured to pale yellow, with green venation. Male flowers mostly occur in racemes with 1 or 2 solitary flowers on the same node. Female flowers are solitary, glabrous, with long articulate trichomes.

The fruits are many-seeded globose berries, 10 mm in diameter at maturity. Ovoid fruits may also occur, especially in more humid habitats. Immature fruits often have white, pale green or dark green longitudinal lines. The white spots or lines become surrounded by a dark green halo during ripening. The mature fruit is usually uniformly coloured red. Ripening usually occurs from green with or without mottling, to yellow to orange, the final colouration. Colour changes from the apex of the fruit downwards. The seeds are ovate, with a flat surface, beige to greyish, with a small margin, which often has a darker colouration.

Flowering time is in summer, October–April.