TiNb-based shape memory alloys (SMAs) have great potentials in biomaterials. However, high transition temperature or small recoverable strain limit their application. Using first-principles method, we systematically study the recoverable strain and transition temperature of TiNb-based binary, ternary, and high-entropy alloys (HEAs), and aim to lower the transition temperature and improve the recoverable strain at the same time. We find that the employed approach describes accurately the lattice strain by comparing with the available experimental results. It is well known that there is a positive correlation between lattice strain and recoverable strain in SMAs. Thus, we have evaluated the magnitude of recoverable strain of SMAs by calculating the lattice strain. Meanwhile, we correlate the available measured martensitic transformation start temperature (M-s) with the calculated energy difference between beta and alpha'' phases in Ti-Nb binary alloys. According to this relation, we evaluate the M-s in other TiNb-based alloys. We find that Zr is a good alloying element that can decrease considerably the M-s and keep the lattice (recoverable) strain almost unchanged simultaneously. Finally, an Al-containing Ti24Nb25Zr24S24Al3 HEA has been designed to have simultaneously large recoverable strain and low transition temperature.