A Lendvai Labdarúgó Klubot 1903. május 11-én alapították. Az első barátságos mérkőzést 1913. augusztus 3-án játszották. Az első tét-mérkőzés pedig 1920-ban Muraszombaton volt, ahova lovaskocsival érkeztek a játékosok. 1935-ben a klub igazi labdarúgó-pályát kapott, hiszen addig az esernyőgyárral szembeni réten játszottak. A második világháború alatt a klub a szombathelyi színekben játszott. A háború vége után a maribori körzetben versenyeztek és 1946-ban elnyerték Szlovénia bajnoki címét. Ekkor a klub új nevet kapott, ez volt NK Nafta. A belgrádi Crvena zvezda elleni 1947-es mérkőzést nem játszották le, mivel a Nafta pénzügyi nehézségek miatt lemondta a szövetségi bajnokságon való szereplést.