This thesis presents an exploration of stars and gas in the halo of our Galaxy. A sample of 8321 field horizontal branch (FHB) stars was selected from the Hamburg/ESO Survey. The stars make excellent tracers of the Milky Way halo, and we studied the kinematics of a subset of the HES FHB stars, comparing their velocity dispersions to those predicted by several models. Since these stars are intrinsically luminous, hot and numerous they make ideal probes of the distances to high-velocity clouds (HVCs) - clouds of neutral hydrogen gas whose distances are largely unknown and which do not fit simple models of Galaxy rotation. A catalogue of stars which align with the HVCs was developed. High resolution spectroscopy of 16 such HVC probes with the Magellan telescope has yielded a remarkably tight distance constraint to complex WB. This is one of only a handful of such distance limits so far established. Lower distance limits were set for several other clouds. Finally, we have suggested that some of the HVCs may be associated with the accretion onto the MilkyWay of the Sagittarius dwarf galaxy.