Fue fundada en 1985 (según otros datos, el año de fundación del club se considera 1986, aunque el club comenzó a actuar en torneos desde 1985) en Qarshi con el nombre de Geolog («Geólogo»). En la temporada de 1985, participó en la Segunda División Soviética de Fútbol, según los resultados del campeonato, Geolog ocupó el 12.º lugar entre 17 equipos en la 7.ª zona. En la siguiente temporada de 1986, el Geólogo de Qarshi ocupó el último lugar 19 en la séptima zona de la Segunda Liga. En las temporadas de 1987, 1988, 1989, el Geólogo no participó en las ligas de toda la Unión, y aparentemente participó en el Campeonato de la RSS de Uzbekistán.

Después del colapso de la Unión Soviética y la independencia de Uzbekistán en la segunda mitad de 1991, desde 1992 todas las antiguas repúblicas soviéticas que formaban parte de la URSS comenzaron a celebrar sus propios campeonatos nacionales y Uzbekistán no fue la excepción. En 1992, el nombre del club de Qarshi pasó a llamarse Pakhtachi. En la primera temporada en la historia del Campeonato de Uzbekistán, el Pakhtachi se incluyó en la Primera Liga, la segunda en términos de nivel e importancia de la liga de fútbol de Uzbekistán. Al final de la primera temporada de la Primera Liga, el Pakhtachi Qarshi ocupó el noveno lugar entre 16 equipos. En 1993, el club pasó a llamarse Nasaf. Antes de la temporada de 1996, el Nasaf participó en la Primera Liga de Uzbekistán. En 1996, el club de Qarshi se llamaba Dynamo-Nasaf.

Antes de la temporada de 1997, la región de Kashkadar tenía al Mash'al de la ciudad de Muborak, que defendía el honor de la región (provincia) en la Liga más alta de Uzbekistán, pero este fue transferido a la Primera Liga de Uzbekistán (segunda división), y el Nasaf Qarshi ocupaba su lugar en la Liga Superior.

En su debut en la máxima división, el Nasaf acabó el campeonato en el sexto lugar entre 18 equipos. En las temporadas de 1998 y 1999 seguidas ocupó el quinto lugar. En la temporada 2000 terminó tercero. En 2001, repitió su resultado, y en las siguientes tres temporadas seguidas, fue cuarto.

En 2010, el club compró un número de jugadores y cambió su equipo significativamente, así como su entrenador. Además, la sede principal del club se reconstruyó al final de la temporada 2008-2009. El entrenador en jefe Viktor Kumykov fue despedido luego de que el equipo enfrentara derrotas ante los principales oponentes de la liga, el Bunyodkor y Pakhtakor. El 10 de agosto de 2010, Anatoliy Demyanenko, una vez el jugador del año en la antigua URSS y exentrenador del Dynamo Kiev, fue presentado como el nuevo entrenador en jefe durante la primera ronda de la temporada 2009-2010.

En la temporada 2011, el Nasaf representó al país en la Copa AFC y terminó la fase de grupos con un excelente resultado de sexta victoria consecutiva, al vencer a Al Tilal en el último partido de la fase de grupos.^[1]​ En marzo y abril, Nasaf se mantuvo invicto en 12 partidos, ganando 10 y empatando dos, logrando el pase a la final.^[2]​ El 29 de octubre de 2011, en el partido final, Nasaf ganó al Kuwait SC por 2–1 y se convirtió en el primer equipo de Uzbekistán en ganar un título internacional de la AFC.^[3]​ En la Liga de Uzbekistán, el club terminó segundo, jugando el último y decisivo partido de campeonato contra Pakhtakor y anotando un penal de último minuto para empatar 1–1.^[4]​

• Super Liga de Uzbekistán (1): 2024
• Copa de Uzbekistán (4): 2015, 2021, 2022, 2023
• Supercopa de Uzbekistán (3): 2016, 2023, 2024
• Subcampeón de la Super Liga de Uzbekistán (3): 2011, 2017, 2020, 2023
• Subcampeón de la Copa de Uzbekistán (5): 2003, 2011, 2012, 2013, 2016

• Copa de la AFC (1): 2011

• Sitio web oficial
• PFK Nasaf Qarshi Archivado el 19 de noviembre de 2012 en Wayback Machine. en PFL.com
• Archivo Archivado el 18 de diciembre de 2012 en Wayback Machine. - (en alemán)
• Torneos Continentales
• soccerway.com
• Nasaf Qarshi en Telegram