Allerede året efter stiftelsen rykkede NB op i [[Mesterrækken]], hvor det blev til mange intense kampe mod [[Hjørring]], [[Frederikshavn]], [[Viborg]] og [[Holstebro]] m.fl. I [[1958]] blev holdet degraderet til [[Serie 1 (DBU Jylland)|Serie 1]]. Her holdt NB skansen indtil [[1962]], hvor førsteholdet måtte rykke ned i [[Serie 2]] – den laveste placering i foreningens historie.
=== Sportslig fremgang ===
Tilbagevenden til [[Serie 1]] 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.
