The presence of Dark Matter (DM) is required in the universe regulated by the standard general relativistic theory of gravitation. The nature of DM is however still elusive to any experimental search. We discuss here the process of accumulation of evidence for the presence of DM in the universe, the astrophysical constraints for the leading DM scenarios that can be obtained through a multi-frequency analysis of cosmic structures on large scales, and a new strategy related to the search for the nature of the DM with the Square Kilometer Array (SKA).