The stability of constituent phases in multi-component system always plays a prominent role in tailoring their mechanical performance at elevated temperatures. In this work, we highlight a chemical ordering feature in the AlTiVCr1-xNbx (0 <= x <= 1) alloys with body-centered cubic crystal structure. The quantum-mechanical first-principle investigations of these alloys on the elemental distribution identify a family of B2 type of partially ordered configurations. We map out the elastic parameters in detail as a function of composition and temperature for disordered and partially ordered phases. A great sensitivity to the order-disorder transformation is revealed, especially for the Cr-rich system. Our results demonstrate that a proper control of the ordering level in these alloys can facilitate the optimal tuning of their mechanical performance while keeping the density almost unchanged. The study presented here further predicts that these alloys possess high specific stiffness, low thermal expansion, and large elastic softening resistance. It is demonstrated that the considered alloys have thermal and mechanical properties that compete with superalloys and other high temperature structural materials.