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 was 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, became deputy leader of Territory Labor, and 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 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.

Member		Party	Term
	Milton Ballantyne	Country Liberal	1974–1980
	Dan Leo	Labor	1980–1990
	Syd Stirling	Labor	1990–2008
	Lynne Walker	Labor	2008–2016
	Yingiya Mark Guyula	Independent	2016–2020

2016 Northern Territory general election: Nhulunbuy

Party		Candidate	Votes	%	±%
	Labor	Lynne Walker	1,502	44.4	−7.9
	Independent	Yingiya Mark Guyula	1,404	41.5	+41.5
	Country Liberal	Charlie Yunupingu	444	13.1	−16.4
	Independent	Jackson Anni	35	1.0	+1.0
Total formal votes			3,385	97.9	+2.3
Informal votes			73	2.1	−2.3
Turnout			3,458	58.7	−7.3
Two-candidate-preferred result
	Independent	Yingiya Mark Guyula	1,648	50.1	+50.1
	Labor	Lynne Walker	1,640	49.9	−13.8
	Independent gain from Labor		Swing	N/A

• Division profile from the Northern Territory Electoral Commission