Lithium niobate (LiNbO$_3$, LN) plays an important role in holographic storage, and molybdenum doped LiNbO$_3$ (LN:Mo) is an excellent candidate for holographic data storage. In this paper, the basic features of Mo doped LiNbO$_3$, such as the site preference, electronic structure, and the lattice distortions, have been explored from first-principles calculations. Mo substituting Nb with its highest charge state of +6 is found to be the most stable point defect form. The energy levels formed by Mo with different charge states are distributed in the band gap, which are responsible for the absorption in the visible region. The transition of Mo in different charge states implies molybdenum can serve as a photorefractive center in LN:Mo. In addition, the interactions between Mo and intrinsic or extrinsic point defects are also investigated in this work. Intrinsic defects $tt V_{Li}^-$ could cause the movement of the $tt Mo_{Nb}^+$ energy levels. The exploration of Mo, Mg co-doped LiNbO$_3$ reveals that although Mg ion could not shift the energy level of Mo, it can change the distribution of electrons in Mo and Mg co-doped LN (LN:Mo,Mg) which help with the photorefractive phenomenon.