Fishbone-like PbMoO4 nanostructures are successfully obtained via the surfactant-assisted hydrothermal method at 160 C. Polyethylene glycol (PEG2000) is used as the template agent. The nanostructures are characterized via X-ray diffraction, field-emission scanning electron microscopy, Fourier transform infrared spectroscopy, ultraviolet-visible light (UV-Vis) spectroscopy, and photoluminescence (PL) measurements. The PbMoO4 morphology is highly associated with the molecular nature of PEG2000. PbMoO4 nanoparticles obtained from PEG2000 have a fishbone-shaped, scheelite-type tetragonal structure, in which numerous secondary branches vertically grow on both sides of the main stem. The structures exhibit broad PL emission bands with the maximum at 306 and 390 nm when excited at 250 nm. In addition, the UV-Vis absorption edge of the structures is in the 280 to 310 nm region, and the band gap is 4.07 eV. A plausible formation mechanism for the fishbone-like PbMoO4 nanostructures is also discussed.