In many cosmologies dark matter clusters on sub-kiloparsec scales and forms compact subhalos, in which the majority of Galactic dark matter could reside. Null results in direct detection experiments since their advent four decades ago could then be the result of extremely rare encounters between the Earth and these subhalos. We investigate alternative and promising means to identify subhalo dark matter interacting with Standard Model particles: (1) subhalo collisions with old neutron stars can transfer kinetic energy and brighten the latter to luminosities within the reach of imminent infrared, optical, and ultraviolet telescopes; we identify new detection strategies involving single-star measurements and Galactic disk surveys, and obtain the first bounds on self-interacting dark matter in subhalos from the coldest known pulsar, PSR J2144-3933, (2) subhalo dark matter scattering with cosmic rays results in detectable effects, (3) historic Earth-subhalo encounters can leave dark matter tracks in paleolithic minerals deep underground. These searches could discover dark matter subhalos weighing between gigaton and solar masses, with corresponding dark matter cross sections and masses spanning tens of orders of magnitude.