ವಿಕ್ರಮಾದಿತ್ಯ ಮಹಾರಾಜನ ಎರಡನೇ ಪತ್ನಿಯಾದ ತ್ರಿಲೋಕಮಹಾದೇವಿ ಕ್ರಿ.ಶ.7ನೇ ಶತಮಾನದಲ್ಲಿ ಈ ದೇವಾಲಯವನ್ನು ನಿರ್ಮಿಸಿದಳು. ಇದು ಈ ಪ್ರದೇಶದ ಅತ್ಯಂತ ಪುರಾತನವಾದ ದೇವಾಲಯವಾಗಿದೆ. ತಮ್ಮ ಪತಿ ಪಲ್ಲವ ರಾಜರ ವಿರುದ್ಧ ಯುದ್ಧದಲ್ಲಿ ಜಯ ಸಾಧಿಸಿದ ಹಿನ್ನೆಲೆಯಲ್ಲಿ ರಾಣಿ ತ್ರಿಲೋಕಾಮಹಾದೇವಿ ವಿರೂಪಾಕ್ಷ ದೇವಾಲಯದ ನಿರ್ಮಾಣದ ನಂತರ ಮಲ್ಲಿಕಾರ್ಜುನ ದೇವಾಲಯ ನಿರ್ಮಾಣಕ್ಕೆ ಅನುಮತಿ ನೀಡಿದ್ದಳು. ದ್ರಾವೀಡ ಶೈಲಿಯಲ್ಲಿರುವ ವಿರೂಪಾಕ್ಷ ದೇವಾಲಯದ ಶೈಲಿಯಲ್ಲೇ ಈ ದೇವಾಲಯವೂ ಕೂಡ ನಿರ್ಮಿತವಾಗಿದೆ. ಪಟ್ಟದಕಲ್ಲಿಗೆ ಭೇಟಿ ನೀಡುವ ಪ್ರವಾಸಿಗರು ಇಲ್ಲಿಗೂ ಒಮ್ಮೆ ಭೇಟಿ ನೀಡಬಹುದು.
ಈ ದೇವಾಲಯದಲ್ಲೊಂದು ಚಿಕ್ಕ ದೇವಸ್ಥಾನ, ಸಭಾ ಮಂಟಪ ಹಾಗೂ ಗರ್ಭಗೃಹದೊಂದಿಗೆ ಅಂಟಿಚೇಂಬರ್(ಅಂತರಾಳ)ಕೂಡ ಇದೆ. ಇಲ್ಲಿನ ಚಿಕ್ಕ ದೇವಸ್ಥಾನದಲ್ಲಿ ಹಿಂದೆ ಮಹಿಷಾಸುರಮರ್ದಿನಿ ಹಾಗೂ ಗಣೇಶನನ್ನು ಪೂಜಿಸಲಾಗುತ್ತಿದ್ದು ಈಗ ವಿಗ್ರಹಗಳನ್ನು ತೆಗೆಯಲಾಗಿದೆ. ಸಭಾ ಮಂಟಪದ ಕಂಬಗಳಲ್ಲಿ ಪುರಾಣ, ರಾಮಾಯಣ ಹಾಗೂ ಮಹಾಭಾರತದ ಕಥೆಗಳನ್ನು ಚಿತ್ರಿಸಲಾಗಿದೆ. ಮಲ್ಲಿಕಾರ್ಜುನ ದೇವಾಲಯದ ಮತ್ತೊಂದು ಆಕರ್ಷಣೆ ಎಂದರೆ ನಂದಿ ಮಂಟಪ, ಇದರ ಮೇಲೆ ಪುರಾತನ ಕಾಲದ ಸುಂದರ ಕಲಾಕೃತಿಗಳನ್ನು ಕೆತ್ತಲಾಗಿದೆ. ಇದರ ನೆಲ ಅಂತಸ್ತಿನಲ್ಲಿ ಆನೆ, ಕುದುರೆ ಹಾಗೂ ಇತರ ಪ್ರಾಣಿಗಳ ಕಲಾಕೃತಿಗಳನ್ನು ಕೆತ್ತಲಾಗಿದೆ.