Першыя футбольныя каманды ў Наваполацку зьявіліся яшчэ ў 1959 годзе, якія прадстаўлялі трэст №16 «Нафтабуд». Аднак, калі пачаў сваю працу пабудаваны нафтапераапрацоўчы завод, клюб прадпрыемства «Нафтавік» пачаў браць удзел у абланых спаборніцтвах. Да клюбу адрызу прыйшлі посьпехі, то бок, атрымаўшы перамогу ў фінале ў гульні супраць віцебскага «Станкабудаўніку», клюб стаў уладальнікам Кубка Віцебскай вобласьці. На той момант асноўны склад клюбу будаваўся на арэнбурцах, працаўніках Орскага ПНЗ, які прыяжджалі ў Наваполацак паводле пераводу на працу.
У 1965 годзе «Нафтавік» стаўся ўладальнікам Кубак БССР. На шляху да перамогі, былі пасьлядоўна пераадолены магілёўскі «Мэталюрг», зборная Петрыкава й берасьцейскі «Лякаматыў». Аднак у першынстве БССР значных пасьпехаў клюб ня зьведаў. З 1965 па 1974 гады каманда праводзіла ў першым і другім дывізіёнах. У 1966 годзе клюб быў зьняты са спаборніцтваў з-за адсутнасьці турнірнай пэрспэктывы, а сэзоны 1969 і 1970 гадоў і наогул прапусьціў. У 1974 годзе «Нафтавік» узяў свой апошні ўдзел у чэмпіянаце БССР.
У сярэдзіне 1980-х гадоў адбылося адраджэньне клюбу, што сталася заслугай працаўнікоў на прыстасаваньнях комплексу па вытворчасьці вадкіх парафінаў. Новы клюб атрымаў назву «Парэкс». Аднак, як і «Нафтавік», клюб меў аматарскі статус. Празь некалькі гадоў станаўленьня клюбу была вернута папярэдняя назва, такім чынам клюб зноўку быў вернуты ў розыгрышы нацыянальных спаборніцтваў. У 1989 годзе «Нафтавік» атрымаў бронзавыя мэдалі абласнога першынства, на наступны год клюб дамогся другога месца ў абласным спаборніцтве. У 1991 годзе клюб атрымаў назву «Нафтан», і адразу стаўся пераможцам турніру прафзьвязаў БССР.
У 1992—1996 гадох каманда, атрымліваючы фінансавую падтрымку з боку нафтапераапрацоўчага заводу, канчаткова атрымала прафэсійны статус.