Klub powstał 5 marca 1939 roku jako Næstved IF. Swoje pierwsze sukcesy zaczął osiągać w latach 70., gdy w 1972 roku zajął w pierwszej lidze 3. miejsce. W 1980 roku Næstved wywalczył swoje pierwsze wicemistrzostwo Danii, gdy uplasował się w tabeli za Kjøbenhavns Boldklub. Po raz drugi wicemistrzem kraju został w 1988 roku, gdy był drugi w lidze za Brøndby IF. Z kolei w 1994 roku Næstved wystąpił w finale Pucharu Danii, w którym przegrał po rzutach karnych z Brøndby. W 1996 roku klub został przemianowany na Næstved Boldklub. W 2000 roku spadł do trzeciej ligi, po raz pierwszy od 1963 roku. W 2006 roku powrócił do drugiej ligi Danii.
Q – runda eliminacyjna, 1/16, 1/8, 1/4, 1/2 – odpowiednia faza rozgrywek, Grupa – runda grupowa, 1r gr – pierwsza runda grupowa, 2r gr – druga runda grupowa, F – finał, R – runda, PO – play-off
k. – rzuty karne, los. – losowanie, Dogr. – dogrywka, w. – zasada bramek strzelonych na wyjeździe
Dan Andersen
Fortuna Düsseldorf
RWD Molenbeek
PSV Eindhoven
Zenit Petersburg
Békéscsaba 1912 Előre SE
União Leiria
Ton Pentre
Keld Bak
Tomas Žvirgždauskas
