The influence of multi-component alloying on the phase transformation and shape-memory effect was investigated to develop new high-temperature shape memory alloys (HT-SMAs). Four alloys—35Ti–20Pd–15Ni–15Pt–15Zr, 40Ti–20Pd–15Ni–15Pt–10Zr (high-entropy alloys, HEAs), 45Ti–20Pd–5Ni–25Pt–5Zr, and 45Ti–20Pd–10Ni–20Pt–5Zr (medium-entropy alloys, MEAs, at%)—were prepared. At room temperature, the B2 structure was stable in the HEAs, and no martensitic transformation (MT) was observed. However, in the MEAs, an MT from the B2 structure to a B19 structure was clearly observed. The MT temperature of the MEAs was comparable to or higher than those of binary and ternary TiPd alloys. The strengths of both the martensite and austenite phases in 45Ti–20Pd–5Ni–25Pt–5Zr were higher than those in 45Ti–20Pd–10Ni–20Pt–5Zr and ternary TiPd alloys. We attempted to explain the high strength using the δ parameter, which indicates the lattice distortion for various atomic sizes, but a clear correlation was not observed, as there were no significant differences in the δ parameter among the tested alloys. The shape recovery was investigated via a thermal cyclic test under an applied stress in the range of 15–200 MPa. Although a small plastic strain was introduced during the thermal cyclic test, a shape recovery over 80% was obtained for both MEAs. Training, that is, the thermal cyclic test under the same applied stress, was conducted to investigate the change of the irrecoverable strain and the work output. For 45Ti–20Pd–5Ni–25Pt–5Zr, the irrecoverable strain was deleted after 50 cycles, and perfect recovery was obtained. The largest work output (3.5 J/cm3) was obtained under 200 MPa. In 45Ti–20Pd–10Ni–20Pt–5Zr, perfect recovery was obtained from the first cycle. However, the recoverable strain was small, and the largest work output was 1.5 J/cm3 under 200 MPa. The shape recovery of 45Ti–20Pd–5Ni–25Pt–5Zr is promising for new HT-SMAs compared with the ternary Ti–Pd–Zr alloys and other HEA-SMAs.