Candi yang terbuat dari batu pasir (sand stone) ini berada di lembah yang diapit oleh perbukitan kecil. Untuk menuju Candi Kedaton Kabupaten Probolinggo ini harus berjalan melewati perkebunan kopi di kawasan lereng Gunung Hyang.
Berbeda dengan candi di Jawa Timur lainnya, candi ini menghadap ke utara. Pada salah satu pipi tangga bagian depan terdapat angka tahun 1292 Saka (1370 Masehi). Dinding batur candi dikelilingi pahatan relief yang mengisahkan cerita tentang Arjunawiwaha, Garudeya, serta adegan cerita Samba. Pembacaan relief di candi ini dilakukan secara prasawyapata yaitu dengan cara mengirikan candi atau mulai dari sebelah kiri candi dimulai dari sudut barat laut.
Relief cerita Arjunawiwaha terukir pada dinding batur sisi barat mulai dari relief pertama hingga relief ke dua belas. Ringkasan ceritanya sebagai berikut :
Pada suatu ketika, ada seorang raja raksasa bernama Niwatakawaca dari negeri Manimantaka, di sebelah selatan Gunung Semeru, menyerang Kahyangan Suralaya (Keindraan) karena lamaran prabu untuk Dewi Supraba ditolak oleh dewa.
Raja raksasa ini mempunyai kesaktian yang tidak dapat dikalahkan oleh dewa maupun asura, namun masih mungkin untuk dapat dikalahkan oleh manusia yang sakti. Sementara itu Arjuna (Parta) sedang melakukan tapa di Gunung Indrakila.
Para dewa memerintahkan bidadari-bidadari untuk menggoda tapa Arjuna agar bisa membantu para dewa menghadapi Niwatakawaca.
Setelah tiga malam menggoda Arjuna, para bidadari tidak berhasil membangunkan Arjuna dari tapanya, kembali ke Suralaya untuk melapor kepada Dewa Indra. Dewa Indra mengkhawatirkan Arjuna, karena bila diteruskan tapanya akan berbuah moksa dan akan melupakan kekuasaan fana.
Karena itu Dewa Indra akhirnya turun untuk menggagalkan tapa Arjuna dengan menyamar sebagai resi tua, pikun, bongkok, telanjang dan memelas, menemui Arjuna. Arjuna terbangun dari tapanya untuk menemui resi tersebut.
Sang resi berubah wujud kembali dalam bentuk aslinya, yaitu Dewa Indra, dan menyembahlah Arjuna kepada Dewa Indra yang menyambutnya dengan baik dan menasehatinya. Prabu Niwatakawaca yang mendengar kabar bahwa para dewa meminta bantuan Arjuna untuk melawan dirinya, menyuruh abdinya yang bernama Murka untuk membunuh Arjuna. Murka berubah menjadi babi hutan dan mengamuk karena tidak menemukan Arjuna di Gunung Indrakila. Mendengar ada keributan yang disebabkan babi hutan, Arjuna memakai baju zirah, busur dan anak panahnya, keluar dari goa.
Pada saat bersamaan Dewa Siwa menyamar sebagai pemburu di daerah Indrakila. Pemburu juga mengincar babi hutan yang mengamuk itu. Arjuna dan pemburu bersama-sama melepaskan anak panahnya ke arah babi hutan. Kedua anak panah tersebut mengenai babi hutan pada satu tempat yang sama dan menyebabkan babi hutan itu mati.
Arjuna dan pemburu memperebutkan babi hutan tersebut hingga mengakibatkan perkelahian yang sengit dengan panah masing-masing.
Sampai akhirnya pemburu itu berubah wujud kembali menjadi Siwa, dan menyembahlah Arjuna kepadanya.
Selanjutnya Arjuna diberi senjata panah Pasopati oleh Dewa Siwa. Tidak lama kemudian datanglah dua apsara utusan Dewa Indra untuk meminta tolong kepada Arjuna agar membantu para dewa melenyapkan Prabu Niwatakawaca yang menyerang Suralaya. Arjuna berangkat menuju Suralaya yang berada di sebelah timur Gunung Semeru.
Arjuna menghadap Dewa Indra dan diberitahu bahwa Niwatakawaca menyerang Suralaya karena menginginkan Dewi Supraba. Dewa Indra mempertemukan Arjuna dan Dewi Supraba untuk diajak bersama menemui Niwatakawaca dan diminta untuk pura-pura mengabdi kepada Prabu Niwatakawaca untuk mengetahui kelemahannya.
Prabu Niwatakawaca menyambut gembira kedatangan Dewi Supraba untuk mengabdi kepadanya. Dewi Supraba merayu Niwatakawaca untuk mengetahui kesaktian dan kelemahannya di taman Manimantaka. Sang prabu menceritakan bahwa dia memperoleh kesaktian saat bertapa di Gunung Himawan sedangkan kelemahannya terletak di ujung lidahnya.
Setelah mendapat informasi dari Dewi Supraba, Arjuna yang berada di luar taman segera menyerang Prabu Niwatakawaca. Terjadilah peperangan sengit, Prabu Niwatakawaca merasa memenangkan pertempuran dan tertawa terbahak-bahak hingga ujung lidahnya terlihat. Arjuna segera melesatkan anak panah ke ujung lidah prabu, hingga prabu tersebut mati.
Atas jasanya Arjuna dijadikan penguasa atau raja di Suralaya selama tujuh bulan, dan memperoleh Batari Supraba dan Batari Tilottama. (Lap. Inventarisasi 2012)
