Fondé en 1965, le club participe à la V-League pour la première fois de son histoire lors de la saison 1982-1983, qu'il achève à la 6e place de sa poule du premier tour de la compétition. Deux ans plus tard, Nam Dinh est sacré champion du Viêt Nam. Il remporte un second trophée en 2007, en s'imposant en finale de la Coupe du Viêt Nam face à Bình Định. Ce succès lui ouvre les portes de la Ligue des champions de l'AFC 2008 et pour ses débuts en compétition asiatique, Nam Dinh ne parvient pas à remporter l'une des rencontres de groupe, n'obtenant qu'un match nul à domicile face aux Thaïlandais de Krung Thaï Bank FC.
En 2009, Nam Dinh échappe à la relégation après avoir battu Can Tho FC, 3e de V-League 2 mais la saison suivante voit le club terminer à la dernière place du classement, synonyme de descente en deuxième division. Le club joue en V-League 2 lors de la saison 2015, après avoir remporté le titre de champion de troisième division la saison précédente.