The club was founded in 1985 under name Geolog. Since 1997 club plays in highest level League in Uzbekistan. FC Nasaf is one of the leading clubs in Uzbekistan. Nasaf finished in its first season in 1997 Uzbek League 6th. In 2000 club finished third after Neftchi Farg'ona.
The club is often listed as a Top 350 club by IFFHS. It has represented Uzbekistan in continental tournaments where its highest achievement has been reaching semi-finals of Asian Club Championship prior to the launch of the new Asian Champions League.
In 2010, the club bought a number of players and changed its squad significantly as well as the head coach. Moreover, the main venue of the club was reconstructed upon the end of the 2008–2009 season. The head coach Viktor Kumykov was fired after team faced defeats against league main opponents Bunyodkor and Pakhtakor. On August 10, 2010, Anatoliy Demyanenko, once the player of the year in the former USSR and former manager of Dynamo Kyiv, was introduced as the new head coach during the first round break of the 2009–2010 season. Nasaf appoints Anatoliy Demyanenko as head coach.
In the 2011 season, Nasaf represented the country in AFC Cup and finished group stage with excellent result of sixth consecutive victories, beating Al Tilal in last group stage match. In March and April Nasaf went unbeaten in 12 games, winning 10 and drawing two. On October 29, 2011 in Final match Nasaf won Kuwait SC with 2–1 and became the first Uzbekistan team to win the AFC Cup. In Uzbek League club finished second, playing last and deciding match of championship against Pakhtakor and scoring a last-minute penalty to draw 1–1.
On January 13, 2012, IFFHS published the Top 350 club list and Nasaf Qarshi placed on 98th position On 3 March 2012 IFFHS published its rating of Top 400 clubs (1st March 2011 – 29th February 2012) where Nasaf shared 89th place with BATE Borisov.
In the 2013 season, the club finished 3rd after Lokomotiv Tashkent and gained promotion to 2nd qualifying play-off round of 2014 AFC Champions League. In Uzbek Cup club played in final 3rd time in row and lost to Bunyodkor with 1–2. On 8 February 2014 in Doha in 2014 AFC Champions League qualifying play-off match against El Jaish Nasaf lost by 5–1. Nasaf finished 2015 season again third and secured place in AFC Champions League in 2015. The club won in 2015 for the first time in its history Uzbek Cup, defeating Bunyodkor by 2–1 in final match on 17 November 2015 in Jizzakh.
Nasaf plays its home matches at the Markaziy Stadim which was built in 2006. The first match at the new stadium was played between Nasaf Qarshi and Uz-Dong-Ju Andijon on August 8, 2008. The stadium was the venue of the AFC Cup final on October 29, 2011.