Nogometni klub Lendava je bil ustanovljen 11. maja 1903, prva prijateljska tekma je bila odigrana 3. avgusta 1913. Prva prava tekma pa leta 1920 v Murski Soboti, kamor so se igralci pripeljali s konjsko vprego. Leta 1935 je klub dobil tudi pravo nogometno igrišče, saj so do takrat igrali na travniku nasproti dežnikarne. Med drugo svetovno vojno je klub igral v sklopu zveze v Sombotelu. Po koncu vojne so začeli tekmovati v mariborskem okrožju in leta 1946 osvojili naslov prvaka Slovenije. Takrat se je klub preimenoval v NK Nafta. Tekma proti beograjski Crveni zvezdi leta 1947 ni bila odigrana, saj je Nafta zaradi finančnih težav odstopila od tekmovanja v zvezni ligi.