Stars in their late stage of evolution, such as Horizontal Branch stars, are still largely unexplored for planets. We report the detection of a planetary companion around HIP 13044, a very metal-poor star on the red Horizontal Branch, based on radial velocity observations with a high-resolution spectrograph at the 2.2-m MPG/ESO telescope. The star's periodic radial velocity variation of P=16.2 days caused by the planet can be distinguished from the periods of the stellar activity indicators. The minimum mass of the planet is 1.25 Jupiter masses and its orbital semi-major axis 0.116 AU. Because HIP 13044 belongs to a group of stars that have been accreted from a disrupted satellite galaxy of the Milky Way, the planet most likely has an extragalactic origin.