Die älteste noch erhaltene Urkunde, die Randa erwähnt, geht auf das Jahr 1305 zurück. Randa bedeutet so viel wie Rand, Grenze. Bis 1552 gehörte Randa zusammen mit Täsch zum Meiertum Naters, später zur Kastlanei Naters. Im Jahr 1590 wurden die Gemeindestatuten errichtet. 1798 wurde Randa eine eigenständige Gemeinde.

Das kleine Bergdorf Randa wurde in den vergangenen Jahrhunderten immer wieder von Naturkatastrophen heimgesucht, so 1636, 1720, 1737, 1819 oder 1991.

Bergsturz von Randa
Die schlimmste Katastrophe für Randa war der Bergsturz im Jahr 1991. Am frühen Morgen des 18. Aprils stürzten riesige Felsbrocken beim Grossgufer (walliserdeutsch für eine «Ansammlung grosser Felsblöcke») ins Tal. Am 9. Mai, drei Wochen später, rutschte der Berg weiter ab; die Geröllmassen von insgesamt ca. 33 Mio. m³ (zum Vergleich: Volumen der Cheopspyramide: 2,5 Mio. m³) begruben grosse Teile des Weilers Lerch mit 33 Landwirtschaftsgebäuden und Ferienhäusern sowie sieben Pferden und 35 Schafen, die Hauptstrasse nach Täsch und die Strecke der Brig-Visp-Zermatt-Bahn. Eine mehrere Zentimeter hohe Staubschicht bedeckte das Tal. Menschen kamen nicht ums Leben.

Auch die durch das Tal fliessende Matter Vispa wurde durch das Geröll gestaut und bedrohte mit ihren Wassermassen den Ort. Das Wasser wurde daraufhin mit elektrischen Pumpen über das Hindernis geleitet. Nach langen Regenfällen verschüttete der Dorfbach mit seinen mitgeführten Geröllmassen die Pumpen, die daraufhin ausfielen. Die tiefer gelegenen Ortsteile Randas wurden am 16. Juni 1991 überschwemmt.