We present a scenario for non-thermal production of dark matter from evaporation of primordial black holes. A period of very early matter domination leads to formation of black holes with a maximum mass of $\simeq 2 \times 10^8$ g, whose subsequent evaporation prior to big bang nucleosynthesis can produce all of the dark matter in the universe. We show that the correct relic abundance can be obtained in this way for thermally underproduced dark matter in the 100 GeV-10 TeV mass range. To achieve this, the scalar power spectrum at small scales relevant for black hole formation should be enhanced by a factor of ${\cal O}(10^5)$ relative to the scales accessible by the cosmic microwave background experiments.