The current club was founded in 2002 after another club from Sevastopol Chaika Sevastopol was relegated from professional ranks and dissolved. FC Sevastopol started out from the Ukrainian Second League and soon was promoted to the Ukrainian First League in 2007. In 2010–11 the club took part in the Premier League of Ukraine for the first time. The club was relegated in its first season back in the Ukrainian First League once more. But the club returned to the Ukrainian Premier League after one season there in which they won promotion to the Ukrainian Premier League.
The club's colours are all red (home) and all dark blue (away).
For the first half of the 2009–10 season the home ground of the club was located outside the Sevastopol city limits. FC Sevastopol played at the Druzhba Stadium located in Bakhchisaray, Crimea. After the winter break they returned to their home ground SK Sevastopol. There are promises to rebuild the Hirnyk Stadium in Balaklava, which is part of the Sevastopol municipality. The reconstruction of Hirnyk is predicted to take place some time in the future.