Atomic ordering in bcc and hcp TiAl+Mo alloys near equiatomic TiAl composition is investigated by different ab initio tools. We show that small addition of Mo, about 5 at. %, is enough to make bcc alloys with more than 50 at. % of Ti stable with respect to the hcp alloys. Moreover, such alloying also leads to stabilizing the B2 ordered structure with respect to its B2(2) modification, which is the bcc-based ground state structure of binary TiAl. The site preference of Mo in the B2 and B19 ordered alloys is investigated by different methods: in the dilute limit, using the transfer energy formalism; in concentrated alloys, from the total energies of disordered and partially ordered alloys in the mean-field coherent potential approximation; and from Monte Carlo simulations. These methods produce consistent results for the B2 phase predicting a strong preference of Mo to Al sublattice. The site preference of Mo in the B19 phases varies from a weak preference for Al sites in the single impurity calculations to a quite strong preference for Ti sites in the mean-field approximation and finally to a strong Al preference in Monte Carlo simulations. Mo alloying dramatically increases the order-disorder transition temperatures in bcc and hcp Al-deficient Ti0.5Al0.5-xMox alloys.