The discovery of high-temperature superconductivity in Fe-based compounds triggered numerous investigations on the interplay between superconductivity and magnetism, and on the enhancement of transition temperatures through interface effects. It is widely believed that the emergence of optimal superconductivity is intimately linked to the suppression of long-range antiferromagnetic (AFM) order, although the exact microscopic picture remains elusive because of the lack of atomically resolved data. Here we present spin-polarized scanning tunnelling spectroscopy of ultrathin FeTe1-xSex (x=0, 0.5) films on bulk topological insulators. Surprisingly, we find an energy gap at the Fermi level, indicating superconducting correlations up to Tc∼6 K for one unit cell FeTe grown on Bi2Te3, in contrast to the non-superconducting bulk FeTe. The gap spatially coexists with bi-collinear AFM order. This finding opens perspectives for theoretical studies of competing orders in Fe-based superconductors and for experimental investigations of exotic phases in superconducting layers on topological insulators.