President Donald Trump har ifrågasatt neutraliteten hos Mueller, som utsågs att undersöka rysk inblandning i det amerikanska valet.
Han har också anklagat justitieminister Jeff Sessions för mr Muellers sond.
Graham varnade Trump för att avskedandet av Mueller "skulle vara början på slutet" av hans ordförandeskap.
"Alla ansträngningar att gå efter Mueller kan vara början på slutet av Trump ordförandeskapet om inte Mueller gjorde något fel," Mr Graham berättade reportrar på torsdag.
Trump administrationen har försökt misskreditera Mr Mueller över hans vänskap med tidigare FBI-chef James Comey, som hade varit på väg utredningen tills han avskedades av Mr Trump i maj.
Presidenten har också föreslagit att Muellers advokatlag skulle kunna vara partiskt eftersom vissa hade bidragit med kampanjinsatser till demokraterna.
Av Anthony Zurcher, BBC News, Washington
Det finns ingen som vet om Lindsey Grahams lagstiftning isolerar den oberoende advokat Robert Mueller från Donald Trump vrede kommer att gå någonstans. South Carolina Republikanen har varit känd för att ibland vandra från senaten flock.
Ändå kan detta vara de första glimrarna av tvåpartisan kongressens ansträngningar att bygga en hinderspärr runt Trump ordförandeskapet.
Redan verkar det troligt att ett lagförslag som hindrar Donald Trump från att ensidigt lossa nuvarande Ryssland sanktioner kommer att hamna på presidentens skrivbord. Trots administrationens invändningar om att detta strider mot verkställande utrikespolitiska privilegier har knappast några kongressledamöter röstat emot lagstiftningen.
Nu, mitt i oron att Mr Trump kan avskeda justitieminister Jeff Sessions som ett sätt att komma åt Mr Mueller, en annan uppsättning handbojor kan tillämpas.
Vita huset verkar vara omgjorda för krig mot dem som undersöker ryska inblandning i 2016 års val och eventuella kopplingar till Trump kampanjen. Chanserna är denna mer aggressiva hållning, inklusive en presidentfejd med Sessions - som tjänstgjorde i den amerikanska senaten i 20 år - kommer dock bara att förvärra situationen.
Som en person fångad i kvicksand, ju mer presidenten kämpar, desto djupare sjunker han.
Mueller har inte gett några detaljer om sin utredning, men USA: s media har rapporterat att han utreder Trump för ett eventuellt hinder för rättvisa, både vid avfyrandet av Mr Comey och om Trump försökte avsluta en undersökning om avskedad nationell säkerhetsrådgivare Michael Flynn.
President Trump har upprepade gånger förnekat någon samverkan med Ryssland, kallar det en "witch jakt".
South Carolina Republican meddelade att han skapade en åtgärd som syftar till att skydda Mr Mueller genom att ålägga att eventuella särskilda ombud som utsetts för att utreda en president eller hans personal inte kunde avskedas "om du har rättslig prövning av avfyrandet".
Han tillade att Mr Trump korsade en "röd linje" i hans övervägande att yxa Mr Mueller, som utsågs av justitiedepartementet för att leda sonden efter att Mr Comey avfyrades.
Grahams varning kommer när presidenten upprepade gånger har angripit justitieministern Jeffs sessioner, som drog sig tillbaka från Rysslands utredning efter att ha underlåtit att avslöja ett möte med Kremls sändebud under sin utfrågning.
Herr Sessions, känd för sin hårdnackade anti-invandringsposition, var en av då kandidaten Mr Trumps tidigaste anhängare i Washington.
Tidigare i veckan sade Trump att han var "nedslagen" med herr Sessions, tweeting att han hade " tagit en mycket svag ståndpunkt" om utredningen av Hillary Clintons användning av en privat e-postserver medan hon var utrikesminister.
I en intervju med New York Times beklagade ordföranden utnämningen av Sessionerna och tillade att han aldrig skulle ha avböjt sig själv.
Anthony Scaramucci, presidentens nya kommunikationsdirektör, underblåste branden på tisdagen genom att föreslå att justitieministerns dagar kunde räknas.
Graham på onsdag sa "det kommer att finnas ett heligt helvete att betala" om Sessions avskedas och varnade för att det skulle bli "ingen bekräftelse för en ny allmän åklagare 2017".
"Detta är inte bara en avledningsmanöver, detta är oroande," sade han reportrar. "Det är orättvist mot Jeff Sessions, han är en bra man som förtjänar bättre, och några av förslagen presidenten ger går långt utöver vad som är acceptabelt."
Senator Lindsey Graham har sagt att han utarbetar lagstiftning för att stoppa alla försök av Trump administrationen att sparka Ryssland utredare Bob Mueller.