Abstract: I will present the first observational estimate of the large-scale distribution of cosmic-ray (CR) nuclei in the halo of the Milky Way, achieved through gamma-ray observations of high- and intermediate velocity clouds by the Fermi Large Area Telescope. CRs up to at least PeV energies are usually described in the framework of an elementary scenario that involves acceleration by supernova remnants or superbubbles in the Milky Way disk, and then diffusive propagation throughout the Galaxy and its halo. The details of the propagation process are so far mainly constrained indirectly by the composition of CRs in the solar system, and then extrapolated to the whole Galaxy. The densities of CR nuclei in remote locations, on the other hand, can be traced via the gamma rays they produce in inelastic collisions with clouds of interstellar gas. Recently, we performed a search for gamma-ray emission from several high- and intermediate-velocity clouds located in the halo of the Milky Way up to ~ 7 kpc from the disk. The gamma-ray emission rate per hydrogen atom was found to decrease with distance from the disk, which provides direct evidence that CRs at the relevant energies originate therein. Furthermore, I will discuss how the results call for a critical reexamination of propagation models against other direct and indirect observations of CRs.