The municipality (originally the parish) is named after the island, Randøen (now known as Randøya). The first part of the name is rand (Old Norse: rǫnd) which means "boundary" or "edge" and the last part of the name is sund which means "strait". The name was previously spelled Randøsund.
The municipality was established on 31 December 1893 when it was split off from the municipality of Oddernes to form a separate municipality. At that time, Randesund had a population of 1,133. On 1 January 1965, Randesund was incorporated into the neighboring municipality of Kristiansand along with neighboring Tveit and Oddernes. Prior to the merger, Randesund had a population of 1,672.