In this paper, we propose and demonstrate an all-fiber passively Q-switched erbium doped fiber laser (EDFL) by using gold nanostars (GNSs) as a saturable absorber (SA) for the first time, to the best of our knowledge. In comparison with other gold nanomorphologies, GNSs have multiple localized surface plasmon resonances, which means that they can be used to construct wideband ultrafast pulse lasers. By inserting the GNS SA into an EDFL cavity pumped by a 980 nm laser diode, a stable passively Q-switched laser at 1564.5 nm was achieved for a threshold pump power of 40 mW. By gradually increasing the pump power from 40 to 120 mW, the pulse duration decreases from 12.8 to 5.3 μs and the repetition rate increases from 10 to 17 kHz. Our results indicate that the GNSs are a promising SA for constructing pulse lasers.