Pasukan bola sepak Negeri Sembilan mula ditubuhkan pada 1923 menurut satu petikan dalam buku sejarah bola sepak Malaysia melalui temuramah dengan Austin Senevirathe, yang berusia 93 tahun semasa ditemuramah. Beliau menyatakan sebuah perlawanan berlaku antara PBNS dan Singapura bagi Piala Malaya (kini: Piala Malaysia) yang berlangsung pada tahun tersebut.

Pasukan ini dikira salah satu kelab yang memberi saingan kuat dalam sejarah bola sepak sejak ditubuhkan. Mereka telah memenangi banyak kejuaraan teratas di Malaysia sejak awal 1940-an.

Pada 7 November 2009, pasukan ini mengakhiri kemarau 61 tahun mereka dalam Piala Malaysia selepas menumpaskan Kelantan dengan nilai mata 3-1 dalam perlawanan akhir yang berlangsung di Stadium Nasional Bukit Jalil.

Ulangan perlawanan akhir 2009 antara kedua-dua pasukan berlaku semula pada tahun berikutnya, 30 Oktober 2010. Walau bagaimanapun, pasukan ini tewas 2-1 kepada Kelantan walaupun pada awalnya telah mendahului dengan sepakan penalti daripada Shahurain Abu Samah.[4]

Pada 2011, pasukan ini sekali lagi layak ke peringkat akhir Piala Maaysia untuk kali ketiga berturut-turut dengan jurulatih baharu mereka, Mohd Azraai Khor Abdullah. Mereka menang perlawanan tersebut selepas menumpaskan Terengganu FA dengan kemunculan semula yang epik. Gol pertama disumbangkan oleh Mohd Ashaari Shamsuddin untuk Terengganu pada minit ke-59. Negeri Sembilan menggunakan 10 minit terakhir untuk lakukan kebangkitan semula. S. Kunanlan menyamakan gol pada minit ke-81 sebelum Hairuddin Omar, penyerang veteran menyepak gol kejuaraan buat Negeri Sembilan dengan tendangan cantik pada minit ke-85.[5]

Pada awal musim 2011, salah satu jurulatih terbaik pasukan, Wan Jamak Wan Hassan telah meletak jawatan daripada kelab ini. Beliau melihat tiada alasan untuk mengecewakan pasukan dalam pertandingan Liga Super Malaysia dan Piala FA Malaysia untuk musim tersebut.[6]

Bermula tahun 2019, pasukan ini tersingkir daripada Liga Super Malaysia, dan bertanding dalam saingan Liga Premier Malaysia.

Sehingga tahun 2020, pasukan ini bertanding atas kapasiti persatuan bola sepak. Namun, akhirnya pasukan ini berjaya diswastakan dalam kempen penswastaan kelab bola sepak oleh FAM pada September 2020 dan akan beraksi sebagai FC bermula musim 2021.