A head-tail high-velocity cloud (HVC) is a neutral hydrogen halo cloud that appears to be interacting with the diffuse halo medium as evident by its compressed head trailed by a relatively diffuse tail. This paper presents a sample of 116 head-tail HVCs across the southern sky (d < 2 deg) from the HI Parkes All Sky Survey (HIPASS) HVC catalog, which has a spatial resolution of 15.5 arcmin (45 pc at 10 kpc) and a sensitivity of N_HI=2 x 10^(18) cm^(-2) (5 sigma). 35% of the HIPASS compact and semi-compact HVCs (CHVCs and :HVCs) can be classified as head-tail clouds from their morphology. The clouds have typical masses of 730 M_sun at 10 kpc (26,000 M_sun at 60 kpc) and the majority can be associated with larger HVC complexes given their spatial and kinematic proximity. This proximity, together with their similar properties to CHVCs and :HVCs without head-tail structure, indicate the head-tail clouds have short lifetimes, consistent with simulation predictions. Approximately half of the head-tail clouds can be associated with the Magellanic System, with the majority in the region of the Leading Arm with position angles pointing in the general direction of the movement of the Magellanic System. The abundance in the Leading Arm region is consistent with this feature being closer to the Galactic disk than the Magellanic Stream and moving through a denser halo medium. The head-tail clouds will feed the multi-phase halo medium rather than the Galactic disk directly and provide additional evidence for a diffuse Galactic halo medium extending to at least the distance of the Magellanic Clouds.