If the dark matter particle is a neutralino then the first structures to form are cuspy cold dark matter (CDM) haloes collapsing after redshifts z ~ 100 in the mass range 10^{-6} - 10^{-3} Msun. We carry out a detailed study of the survival of these micro-haloes in the Galaxy as they experience tidal encounters with stars, molecular clouds, and other dark matter substructures. We test the validity of analytic impulsive heating calculations using high resolution N-body simulations. A major limitation of analytic estimates is that mean energy inputs are compared to mean binding energies, instead of the actual mass lost from the system. This energy criterion leads to an overestimate of the stripped mass and underestimate of the disruption timescale since CDM haloes are strongly bound in their inner parts. We show that a significant fraction of material from CDM micro-haloes can be unbound by encounters with Galactic substructure and stars, however the cuspy central regions remain relatively intact. Furthermore, the micro-haloes near the solar radius are those which collapse significantly earlier than average and will suffer very little mass loss. Thus we expect a fraction of surviving bound micro-haloes, a smooth component with narrow features in phase space, which may be uncovered by direct detection experiments, as well as numerous surviving cuspy cores with proper motions of arc-minutes per year, which can be detected indirectly via their annihilation into gamma-rays.