Titanium aluminides are technologically important intermetallic alloys with also many curious properties interesting from a basic research point of view. When alloyed with Mo, several (meta)stable phases have been reported; their properties are, however, largely unknown due to the alloy processing (e.g. fast cooling) and/or non-existence as a single-phase material. Here we employ first principles calculations to study compositional trends in structural and mechanical properties. We could show that Mo increases the density of all studied phases, leads to their chemical destabilization with the exception of the ordered bcc β _o phase, increases their ductility, and enhances the elastic anisotropy. Discrepancies between two employed ab initio methods (special quasi-random structures vs. coherent potential approximation) in the case of the β _o and B19 phases are rationalized with significant local distortions which may eventually facilitate a spontaneous phase transformation. Predictions of ordering temperatures solely based on the configurational entropy do not yield values in the experimentally expected ranges.