Il Nautara è stato fondato nel 1998 da Gerardas Pasažauskas[1] come squadra di calcio, ma dopo appena due anni la società si è convertita al calcio a 5. Durante la presidenza di Pasažauskas, il Nautara ha vinto sei edizioni del campionato lituano di calcio a 5, l'ultimo dei quali nella stagione 2012-13. Il debutto nella Coppa UEFA risale all'edizione 2005-06, nella quale i lituani sono stati eliminati nel turno preliminare. La qualificazione al primo turno della manifestazione continentale è stato raggiunto nell'edizione 2008-09 nella quale il Nautara ha vinto il girone preliminare precedendo i moldavi della Dinamo Chișinău , gli albanesi del Tirana e i danesi dell'Albertslund. Al termine della stagione 2013-14 Pasažauskas annuncia la propria fuoriuscita dalla società, che dalla stagione seguente adotta la denominazione "FK Celsis"[1].