Nhulunbuy was an electoral division of the Legislative Assembly in Australia's Northern Territory. It was first created in 1974, and is named after the remote town of the same name. Nhulunbuy is a rural electorate on the Territory's northeast coast, covering 113,600 square kilometres (43,900 sq mi) and taking in the towns of Nhulunbuy, Galiwinku, Yirrkala and Gapuwiyak. There were 5,895 people enrolled in the electorate as of August 2016. The division was abolished in 2020, and replaced by the division of Mulka.

Nhulunbuy was traditionally a safe seat for the Labor Party, which held the seat without a break from 1980 to 2016. Labor's dominance in the seat was mostly on the strength of strong support among indigenous voters; more than 50% of the electorate's population being indigenous. The only exception to the ALP's dominance was Milton Ballantyne, who won the seat for the Country Liberal Party in 1974 when the ALP won no seats in the Assembly. Ballantyne managed to hold on despite a strong swing to the ALP in 1977, before being easily beaten by the ALP's Dan Leo in 1980. Leo retired in 1990 and handed the seat to Syd Stirling, who went on to become deputy leader of Territory Labor, and as such became Deputy Chief Minister under Clare Martin from 2001 to 2008. Stirling stood down in 2008 and was succeeded by Lynne Walker, who became deputy opposition leader in 2015.

With Labor being an unbackable favourite to win the 2016 Territory election, Walker appeared well on her way to becoming Deputy Chief Minister. Even without Labor being heavily favoured to win government, there was virtually no hint that Walker was in any danger in her own seat, which she held with a seemingly insurmountable 13.7 percent majority. However, in a shock result, even as Labor swept to a landslide victory, Walker was defeated by independent and indigenous activist Yingiya Mark Guyula by just eight votes, making the seat Labor's only loss in the election.