Tilbagevenden til [[Serie 1980]] kom dog allerede efter kun en sæson, og hermed var der sat en milepæl for en længerevarende sportslig fremgang. Et par år senere rykkede holdet op i Jyllandsserien, men måtte forlade den igen efter en enkelt sæson. Et meget talentfuldt kuld ynglinge med bl.a. [[Henning Jensen (fodboldspiller)|Henning Jensen]] og [[Poul Erik Andreasen]] kom herefter ind i billedet, og allerede i deres andet år sikrede de igen oprykning til [[Jyllandsserien]] samt det jyske mesterskab i [[Serie 1]]. I [[1969]] blev NB et af de første hold, som udnyttede [[Dansk Boldspil-Union|DBU]]’s nye reklamebestemmelser ved at bære reklamer på opvarmningsdragterne. Det lokale grovvareselskab [[Peder P. Hedegaard (virksomhedsejer)|Peder P. Hedegaard]] indgik en tre års kontrakt og ydede 250,00 kr. pr. kamp til 12 markspillere samt 6 bolddrenge. Samme år henvendte en flok interesserede piger sig for at få lov at spille fodbold indenfor klubbens rammer, og dermed blev NB formentlig den første klub i byområdet med pigefodbold på programmet. I [[1970]] spillede NB uafgjort mod [[Skive IK|Skive]] i årets sidste kamp og mistede derved oprykning til [[Danmarksserien]]. Men året efter vandt holdet den afgørende kamp på [[Taars Stadion (Nordjylland)|Taars Stadion]] med 3-1, og var hermed for første gang i [[Danmarksserien]]. I sommerpausen [[1972]] skrev [[Henning Jensen]] kontrakt med [[Borussia Mönchengladbach]], og var dermed tabt såvel for NB som for landsholdet. Det var medvirkende til, at holdet igen måtte forlade [[Danmarksserien]] efter en enkelt sæson.
