In this letter we report on proximity superconductivity induced in CdTe-HgTe core-shell nanowires, a quasi-one-dimensional heterostructure of the topological insulator HgTe. We demonstrate a Josephson supercurrent in our nanowires contacted with superconducting Al leads. The observation of a sizable $I_c R_n$ product, a positive excess current and multiple Andreev reflections up to fourth order further indicate a high interface quality of the junctions.