A novel three-dimensional (3D) nanocomposite based on Na0.9Mg0.45Ti3.55O8 (NMTO) nanoplates and few layered MoS2 nanosheets was fabricated via a facile two-step hydrothermal process. The few-layer MoS2 nanosheets were uniformly loaded on NMTO nanoplates to form a 3D hierarchical structure. The as-obtained MoS2/NMTO composites exhibit superior photocatalytic activities for stably photodegradating methylene blue (MB) and methyl orange (MO) in comparison with pure MoS2 nanoflowers and pure NMTO nanoplates. Importantly, the MoS2/NMTO heterostructure with 30wt% of MoS2 shows the highest performance in photocatalytic degradation of dye molecules. The formation of 3D hierarchical heterostructure between few-layer MoS2 nanosheets and NMTO nanoplate favors the separation of photoinduced electron-hole pairs and contributes to the enhanced photocatalytic properties.