Niobium-based alloys are envisioned as promising candidates for high-temperature turbine materials. In this study, we have used the Bayesian optimization algorithm to guide us in searching for suitable niobium-based alloy compositions with optimized mechanical strengths. Several well-known machine learning models combined with different material descriptors are trained to predict the targeted mechanical properties. We recommend that the domain knowledge-based material descriptors are very effective for predicting the targeted properties in the case of sparse datasets. We have provided a design strategy for individual optimization of yield strength and ultimate tensile strength and simultaneous optimization of both properties. We believe that our design strategy for candidate selection in a vast compositional space will accelerate the alloy development process.