NSi je nastala 4. avgusta 2000, nekaj mesecev po tem, ko sta se po dolgih letih prizadevanj združili takratni vladna SLS in opozicijski Slovenski krščanski demokrati (SKD). Z združitvijo je razpadla takratna vladna koalicija (LDS, SLS in DeSUS), kasneje po združitvi pa sta združena stranka in SDS uspeli oblikovati koalicijo. Mesto mandatarja je pripadlo najmočnejši stranki, ki je za ta položaj predlagala dr. Andreja Bajuka. V dveh tajnih glasovanjih ta ni dobil zadostne podpore, v tretjem, javnem glasovanju 3. maja 2000, pa je bil potrjen s 46 glasovi za in 44 proti. Celotna vlada je bila v Državnem zboru potrjena 7. junija 2000, v njej je Lojze Peterle postal zunanji minister.

Mesec dni po imenovanju nove vlade so vsi poslanci SLS+SKD glasovali za ustavni zakon, ki naj bi uveljavil proporcionalni volilni sistem, čeprav je bil dogovor ob združitvi strank drugačen. Takratna podpredsednika združene stranke  dr. Bajuk in Peterle sta  vztrajala pri uveljavitvi referendumske volje državljanov, ki so glasovali za večinski volilni sistem.

Zaradi neupoštevanja dogovora in referendumske volje državljanov sta v tednu po glasovanju Bajuk in Peterle izstopila iz SLS+SKD in 4. avgusta 2000 v polni dvorani ZZZS na Miklošičevi cesti v Ljubljani ustanovila stranko z imenom Nova Slovenija – Krščansko ljudska stranka. Prvi predsednik novoustanovljene stranke je tako postal dr. Andrej Bajuk.

Dva meseca kasneje leta 2000 je NSi samostojno nastopila na parlamentarnih volitvah in prejela 8,66 odstotkov glasov in tako dobila osem poslancev Državnega zbora RS (dr. Andrej Bajuk, dr. Jožef Bernik, mag. Janez Drobnič, Ivan Mamić, Lojze Peterle, Alojz Sok, Marija Ana Tisovec in Majda Zupan). V mandatnem obdobju 2000-2004 je NSi sestavljala opozicijo takratni Vladi pod vodstvom LDS.

Leto 2001 je NSi zaznamoval prvi redni kongres v Rogaški Slatini, na katerem je bil dr. Bajuk ponovno izvoljen za predsednika stranke, predsednik sveta pa je postal Lojze Peterle. Svet NSi je decembra tega leta izvolil še dva podpredsednika NSi, takratnega poslanca mag. Janeza Drobniča in poslanca Alojza Soka, tretji podpredsednik pa je postal Avguštin Vivod, ki je predstavljal člane NSi v tujini.

V volilnem letu 2002 je stranka na lokalnih volitvah dosegla podoben rezultat kot leta 2000 na parlamentarnih volitvah (8,33 odstotka) in dosegla 254 mandatov v občinah. Za župane je bilo izvoljenih šest kandidatov NSi.
V istem letu je na predsedniških volitvah NSi skupaj s SDS podprla neodvisno kandidatko Barbaro Brezigar, ki je v drugem krogu v tekmi z Janezom Drnovškom prejela 43,5 odstotka glasov.

NSi je tudi v letu 2003 nadaljevala z usklajeno opozicijsko politiko s SDS, ki jo je v začetku leta zaznamovalo "znamenitih" šest zahtev, z uresničitvijo katerih naj bi se povečala stopnja demokracije v Sloveniji. Zahteve so se med drugim nanašale na pluralnost medijev, na enakopravnejšo zastopanost koalicije in opozicije v podjetjih in evroatlantskih institucijah ter pravično razdelitev premoženja nekdanjih družbeno-političnih organizacij.

Leta 2004 so v Sloveniji potekale prve volitve v Evropski parlament. Na njih je NSi zmagala s 23,6 odstotka zbranih glasov volivk in volivcev in tako dobila dve poslanski mesti v Evropskem parlamentu. Evropska poslanca sta postala Lojze Peterle in Ljudmila Novak, ki sta člana politične skupine Evropske ljudske stranke – Evropskih demokratov (ELS-ED).

V jeseni 2004 je na parlamentarnih volitvah leta NSi dobila 9,09 odstotka glasov in  s tem devet poslanskih mest v Državnem zboru RS. (Alojz Sok,  Marjetka Uhan, Martin Mikolič, Drago Koren, Anton Kokalj, Jožef Horvat, dr. Andrej Bajuk, ki je bil imenovan za ministra za finance in ga je tako nadomestil Ciril Testen, mag. Janez Drobnič, ki ga je v času ministrovanja nadomestil mag. Franc Capuder in Mojca Kucler Dolinar, ki jo je v času ministrovanja nadomestila Majda Zupan).

Po volitvah je NSi skupaj s SDS, SLS in DeSUS sestavila vladno koalicijo. NSi je v Vladi RS prevzela štiri odgovorna ministrstva: Ministrstvo za finance RS (minister dr. Andrej Bajuk), Ministrstvo za delo, družino in socialne zadeve RS (minister mag. Janez Drobnič, od decembra 2006 ministrica Marjeta Cotman), Ministrstvo za pravosodje RS (minister dr. Lovro Šturm) ter Ministrstvo za visoko šolstvo, znanost in tehnologijo RS (minister Jure Zupan, od oktobra 2007 ministrica Mojca Kucler Dolinar). Dosežke Nove Slovenije v Vladi RS od 2004 do 2008 si lahko ogledate tukaj.

Na drugem rednem kongresu stranke v Novi Gorici leta 2005 je bil za predsednika ponovno izvoljen dr. Andrej Bajuk, za podpredsednike pa Alojz Sok, mag. Janez Drobnič, ki ga je po izstopu iz stranke leta 2008 nadomestil Nace Polajnar ter evropska poslanka Ljudmila Novak. Kasneje je bil s strani zamejcev in Slovencev po svetu za četrtega podpredsednika NSi imenovan Klemen Žumer.

Na lokalnih volitvah leta 2006 je NSi dosegla 6,33 odstotkov glasov in prejela 190 mandatov v občinskih svetih. Iz njenih vrst je bilo izvoljenih  enajst županov (Miro Cvetko - Sveti Tomaž, Damjan Jaklin - Velka Polana, Rajko Janžekovič - Dornava, Janko Jazbec - Horjul, Milan Kerman - Beltinci, Franci Krepša - Sveti Andraž, Martin Mikolič - Rogatec, Janez Pavlin - Videm-Dobrepolje, Alojz Sok - Ormož, Franc Šlihthuber - Gornji Petrovci in Franc Vovk - Dolenjske Toplice).

Leta 2007 je na volitvah predsednika Republike Slovenije je stranka skupaj s SDS in SLS podprla neodvisno kandidaturo Lojzeta Peterleta za predsednika države, ki je v drugem krogu prejel 31,97 odstotkov glasov.

Na državnozborskih volitvah leta 2008 je NSi dosegla 3,40 odstotkov glasov in tako ni prestopila parlamentarnega praga. Po razglasitvi rezultatov je z mesta predsednika NSi odstopil dr. Andrej Bajuk. Tako je Izvršilni odbor NSi imenoval podpredsednico Ljudmilo Novak za vršilko dolžnosti predsednika do izrednega volilnega kongresa. Tako so delegatke in delegati na izrednem volilnem kongresu 15. novembra v Ljubljani za novo predsednico izvolili Ljudmilo Novak, za podpredsednike Jožefa Horvata, Antona Kokalja in Marjetko Uhan ter za predsednico Sveta stranke  Mojco Kucler Dolinar.

 

Organizacijsko strukturo Nove Slovenije tvorijo organi na nacionalni ravni (kongres, svet, konferenca, izvršilni odbor) in na lokalni ravni (krajevni, občinski in regijski odbori). V stranki delujejo še klub županov in svetnikov, ženska zveza, podmladek Mlada Slovenija, kmečka zveza, zveza seniorjev in združenje delavcev.