We study the possibility to explain the mystery of the dark matter (DM) through the transition from General Relativity to embedding gravity. This modification of gravity, which was proposed by Regge and Teitelboim, is based on a simple string-inspired geometrical principle: our spacetime is considered here as a four-dimensional surface in a flat bulk. We show that among the solutions of embedding gravity, there is a class of solutions equivalent to solutions of GR with an additional contribution of non-relativistic embedding matter, which can serve as cold DM. We prove the stability of such type of solutions and obtain an explicit form of the equations of motion of embedding matter in the non-relativistic limit. According to them, embedding matter turns out to have a certain self-interaction, which could be useful in the context of solving the core-cusp problem that appears in the CDM model.