Air Terjun Madakaripura nyatanya tidak terlepas dari legenda. Konon, tempat ini sebagai peristirahatan terakhir atau pertapaan Patih Gajah Mada pada masa Kerajaan Majapahit.
Pada zaman dahulu kala, Majapahit memberikan Madakaripura sebagai hadiah atas kerja keras Mahapahit dalam membela kerajaan. Selain itu, dia juga sekaligus menghargai tekad dan kerja keras Gajah Mada dalam mempersatukan Nusantara dengan sumpahnya, yaitu yang terkenal dengan sebutan "Sumpah Palapa".
Hal itu diabadikan dengan adanya patung Gajah Mada yang diletakkan di sekitar air terjun. Selain indah, air terjun ini memiliki banyak sejarah.