1872 valgtes han til folketingsmand for Lejrekredsen (Københavns Amts 5. kreds), hvilken han bevarede ved de senere valg, indtil han 1890 frivilligt nedlagde sit mandat. Han kom ind i Rigsdagen ved at slå venstremanden D.E. Rugaard, men i øvrigt som uafhængig politiker. I begyndelsen sluttede han sig i det parlamentariske spørgsmål nærmest til Højre, samtidig med at han i et af de vigtigste da foreliggende realitetsspørgsmål, skolereformen, gik sammen med Venstre, hvis hævdelse af friskoletanken tiltalte ham, også i hans egenskab af katolik. Det var i denne sag, han holdt sin jomfrutale, og den viste ham straks som én af tingets mest fremragende debattører. Kultusminister C.C. Hall, mod hvis forslag talen var rettet, begyndte sit svar med at udtale sin glæde over det nye medlem, som tinget havde fået fra Lejre. 1873 udtalte han sig gentagne gange imod det af Venstre rejste parlamentariske krav og den måde, hvorpå det søgtes gennemført; men ved årets slutning og det følgende år foregik der for så vidt en svingning i hans opfattelse, som han støttede bestræbelserne for et ministerskifte i venstre retning og angreb ministeriet Holstein-Holsteinborg, fordi det ved offentliggørelsen af den håndskrivelse, ved hvilken kongen afslog at modtage ministeriets afskedsbegæring, havde draget statens uansvarlige overhoved ind i partikampen. Stedse stærkere vendte Holstein sig fra nu af mod Højre, og stedse nærmere blev hans forbindelse med Det forenede Venstre, i hvilket han dog først formelt optoges 1875. Det var navnlig de antydninger, som fra Højres presse og flere af dets ledende mænd nu begyndte at fremkomme om provisoriskefinanslovestilladelighed, som fuldbyrdede omslaget. Over for ministeriet Fonnesbech havde Holstein vel følelsen af, at man burde benytte denne regerings forsonlige tendenser til en tilnærmelse mellem partierne, således at de yderste skridt kunne undgås; men da disse forsoningsbestræbelser mødte vanskeligheder i begge lejre, og da ministeriet frembød forskellige sårbare punkter, der alt for meget fristede den behændige polemiker, vendte han snart sine våben også imod det, og fra ministeriet Estrups tiltræden tilhørte han helt og ubetinget oppositionen. Der var lige fra begyndelsen blod mellem Holstein og dette ministerium, måske netop fordi det hovedsageligt var dannet og støttedes af hans standsfæller.
Venstrepolitikeren
Venstre indså til fulde, hvilken fremragende kraft det i Holstein havde erhvervet. Han blev snart en af de mest yndede talere ved de store folkemøder, fx 20. maj1883 i Lejre, og som debattør havde han ikke sin lige i Rigsdagen. Han var i besiddelse af en overordentlig naturlig veltalenhed, en sjælden hurtig og skarp opfattelsesevne og et polemisk talent, som forstod at smede våben for sit parti af enhver sag, og som i smidig vekslen lige let kunne sætte lidenskaben og latteren i bevægelse. Fra 1876 var Holstein blevet medlem af Finansudvalget og var 1877-90 så godt som uafbrudt dettes ordfører. Det var i denne egenskab, han fra nu af vandt sine politiske laurbær. Situationen var jo i disse år som regel storpolitisk tilspidset, og det saglige var i Rigsdagens debatter oftest det ganske underordnede. Stærkt saglig interesseret var Holstein da også kun sjældent, medens netop de ejendommelige krav, som den daværende politiske situation stillede, lod hans særlige evner nå til deres højeste udfoldelse. Med alt det var den fremragende polemiker dog i de afgørende situationer som regel en kompromis'ets og overenskomstens mand. Dette førte ham til i 1877 sammen med Frede Bojsen at forberede og gennemføre Novemberforliget, ligesom han i de følgende år tilhørte den moderate gruppe inden for Venstre og var stærkt medvirkende ved det såkaldte »majforlig« 1882. Senere, da Bojsen nærmede sig Christen Berg, hvis politiske modsætning Holstein altid ville være, indtrådte der en tilnærmelse mellem denne og Viggo Hørup, og det var da også navnlig fra disse to, den første genoptagelse af forhandlingspolitikken efter provisoriet 1885 udgik. Holstein blev i 1884 forsonet med Berg og medvirkede i november 1884 til dannelsen af
Det Danske Venstre, men nærmede sig alligevel Hørup og var ivrig for at tilspidse kampen, hvilket medførte en ny splittelse af Venstre 1885. Ligesom Hørup var Holstein stemt for gennem en tilnærmelse mellem Venstre og Landstingets godsejere ("smørkrigen" 1887-88) at bringe forfatningskampen til afslutning. Hvad der imidlertid gjorde det meget vanskeligt for Holstein at opnå resultater af sin mæglende virksomhed, var, at polemikeren i ham ikke sjældent tog magten fra politikeren. Ofte kunne han ikke stå for fristelsen til skånselsløst at benytte en modstanders blottelse i debatten, selv hvor den oratoriske sejr, han herved kunne vinde, måtte skabe hans politik vanskeligheder af den alvorligste art. At Holsteins velmente forsoningsbestræbelser strandede, var sikkert i høj grad medvirkende til, at han i foråret 1890 trak sig tilbage fra det politiske liv og nedlagde sit mandat, men hvad der også spillede sin rolle her, var den ret isolerede stilling, han efterhånden var kommet til at indtage mellem Venstres indbyrdes stridende grupper. Han hørte ikke helt til i nogen af dem, og når han over for offentligheden stod som det samlede partis ordfører og som en af dets vigtigste ledere, var dette, som han godt selv følte, oftest mere skin end virkelighed. Trods fremragende evner og ubestridelig troskab mod sit partis sag måtte Holstein selv ved sin mandatnedlæggelse 1890 erkende "Forudsætningerne for sin Politik bristede nu og i Fremtiden". Fra nu af, og indtil han 1895 ved sin faders død overtog styrelsen af grevskabet Ledreborg, opholdt Holstein sig mest i udlandet, hovedsagelig i Schweiz, væsentlig beskæftiget med kirkehistoriske studier. Også efter sin tilbagevenden til Danmark holdt han sig ganske udenfor det politiske liv.
Regeringsleder
Efter systemskiftet i juli 1901 takkede han nej til tilbuddet om at blive regeringsleder i den første venstreregering, men da konflikten mellem Niels Neergaard og J.C. Christensen truede både forsvarssagen og det politiske system i det hele taget, indvilligede han efter kraftig overtalelse i august 1909 i at danne en regering, som skulle føre forsvarslovene igennem.
Mellem Venstregrupperne var der truffet en overenskomst om lovenes indhold, som kunne regne på støtte fra så stor en del af Højre, at gennemførelsen var sikret i begge ting, men forudsætningen for overenskomsten var fra Venstres side den, at der i spidsen for ministeriet trådte en venstremand, som var uberørt af de senere års gruppestridigheder. Det, som bestemte Holstein til at træde i spidsen, var ikke nogen udpræget interesse for denne eller hin bestemte løsning af forsvarsspørgsmålet, men ønsket om at undgå den falliterklæring for det parlamentariske system og den dybtgående splittelse inden for det gl. Venstre, som forsvarslovenes stranding ville have haft til følge. 16. august dannede han sit ministerium, i hvilket J.C. Christensen indtrådte som forsvarsminister og Niels Neergaard og de fleste medlemmer af hans ministerium fik sæde. Forsvarslovene gennemførtes (Forsvarsforliget 1909), hvorefter Christensen 18. oktober indgav sin afskedsbegæring, og Holstein, som hidtil ikke havde forbundet nogen anden portefølje med konseilspræsidiet, midlertidig overtog hans stilling, men allerede 28. oktober trådte ministeriet tilbage. Ved finanslovforslagets 1. behandling opstod der en konflikt mellem Højres repræsentant Martin Madsen Halsted og Holstein, foranlediget ved dennes skarpe benægtelse af, at han, som af Højres ordfører i god tro påstået, havde gjort dette partis tilslutning til forsvarsoverenskomsten til betingelse for at danne ministeriet. Konflikten mundede ud i et af Højre stillet forslag til em mistillidserklæring til konseilspræsidenten, som blev vedtaget ved de radikales og socialdemokraternes hjælp og medførte hele ministeriets afgang. Efter sin tilbagetræden deltog Holstein ikke mere i det politiske liv.
Holstein havde således fremprovokeret et flertal for en mistillidsvotum, der blev fremsat af Det radikale Venstre. Holstein bad dernæst Frederik 8. om at henvende sig til det parti, hvis dagsorden havde sejret. Næsten ubemærket i samtiden fik Holstein herigennem demonstreret gyldigheden af parlamentarisk statsskik, og afsluttede dermed sin politiske karriere med en fornem sejr, der for eftertiden må siges at være mindst lige så vigtig som J.C. Christensens forsvarsforlig.[1]
Han døde i 1912 på sit gods, i hvis park han også er begravet. Holstein var ikke dekoreret med Dannebrogordenen, som han formentlig har afslået at modtage.
Han er portrætteret på malerier af August Schiøtt 1867 (Ledreborg) og B. Middelboe 1883 (Folketinget), kopi af førstnævnte af Johannes Ottesen 1930 (Frederiksborgmuseet). Barnebillede med forældre og søskende af Elisabeth Jerichau Baumann 1855 (Ledreborg). Litograferet af I.W. Tegner på gruppebillede af Venstres førere 1885. Træsnit 1875, af I. Falander 1878 og af C. Hammer 1883. Talrige litografiske tegninger til Punch 1886-90.
