Randers, 1898 yılında Randers Freja olarak kuruldu. Girdiği ekonomik kriz sonrası ikinci lige düştü. 1 Ocak 2003 tarihinde de 5 kulüp, birleşerek Randers FC ismini aldı.
2006-2007 sezonunda UEFA Kupası 1. Turu'nda mücadele ettiği Fenerbahçe karşısında deplasmanda aldığı 2-1'lik ve de kendi sahasında aldığı 3-0'lık mağlubiyetlerle (toplamdam 5-1), UEFA Kupası'ndan elendi. Randers, Avrupa kupalarında çıktığı 16 maçta 6 galibiyet, 3 beraberlik ve 7 mağlubiyet aldı. Ayrıca Avrupa kupalarında attığı 22 gole karşılık kalesinde 20 gol gördü.
