Bismuth telluride (Bi_{2}Te_{3}) based thermoelectric (TE) materials have been commercialized successfully as solid-state power generators, but their low mechanical strength suggests that these materials may not be reliable for long-term use in TE devices. Here we use density functional theory to show that the ideal shear strength of Bi_{2}Te_{3} can be significantly enhanced up to 215% by imposing nanoscale twins. We reveal that the origin of the low strength in single crystalline Bi_{2}Te_{3} is the weak van der Waals interaction between the Te1 coupling two Te1─Bi─Te2─Bi─Te1 five-layer quint substructures. However, we demonstrate here a surprising result that forming twin boundaries between the Te1 atoms of adjacent quints greatly strengthens the interaction between them, leading to a tripling of the ideal shear strength in nanotwinned Bi_{2}Te_{3} (0.6 GPa) compared to that in the single crystalline material (0.19 GPa). This grain boundary engineering strategy opens a new pathway for designing robust Bi_{2}Te_{3} TE semiconductors for high-performance TE devices.