In the current cosmological paradigm, Dark Matter (DM) constitutes a large portion (about 27 %) of the mass and energy content of the Universe. One DM candidate, the Weakly Interacting Massive Particle (WIMP), can potentially have a mass in the range from 50 GeV to greater than 10 TeV. Self-annihilation and/or decay of WIMPs may produce various secondary particles, producing very-high-energy gamma rays (VHE; above 100 GeV). The signature of the WIMP signal has been searched with state-of-art observatories, but it has not been successful. This lack of success proposes a new parameter range, ultra-heavy DM (UHDM). In this talk, I will summarize the status of the WIMP search, focusing on the Very Energetic Radiation Imaging Telescope Array System (VERITAS) result, and explore the feasibility of detecting the annihilation signature for UHDM with current and future VHE gamma-ray observatories. Finally, I will present the result of the UHDM search with VERITAS.