The problems of simple elementary weakly interacting massive particles (WIMPs) appeal to extend the physical basis for nonbaryonic dark matter. Such extension involves more sophisticated dark matter candidates from physics beyond the Standard Model (BSM) of elementary particles. We discuss several models of dark matter, predicting new colored, hyper-colored or techni-colored particles and their accelerator and non-accelerator probes. The nontrivial properties of the proposed dark matter candidates can shed new light on the dark matter physics. They provide interesting solutions for the puzzles of direct and indirect dark matter search.