A strained and undoped HgTe layer is a three-dimensional topological insulator, in which electronic transport occurs dominantly through its surface states. In this Letter, we present transport measurements on HgTe-based Josephson junctions with Nb as a superconductor. Although the Nb-HgTe interfaces have a low transparency, we observe a strong zero-bias anomaly in the differential resistance measurements. This anomaly originates from proximity-induced superconductivity in the HgTe surface states. In the most transparent junction, we observe periodic oscillations of the differential resistance as a function of an applied magnetic field, which correspond to a Fraunhofer-like pattern. This unambiguously shows that a precursor of the Josephson effect occurs in the topological surface states of HgTe.