Den 56-årige träffade ordförande Steve Parish på torsdag då spänningen mellan paret kom till ett huvud.
Den tidigare Stoke bossen, som vann Premier Leagues chef för årets utmärkelse förra säsongen, hade varit frustrerad över misslyckandet att landa ett antal sommaröverlåtelsemål.
Mediauppspelning stöds inte på den här enheten
Biträdande chef Keith Millen kommer att vara ansvarig mot Arsenal på lördag.
På fredagen gjorde Palace ett uttalande och sade: "Klubben vill tacka Tony för hans insatser med klubben förra säsongen och önska honom allt gott för framtiden."
Oddsen för bookmakers hade rasat på torsdag när spekulationen om walesiska mannens jobb intensifierades.
Mediauppspelning stöds inte på den här enheten
Malky Mackay och David Moyes föreslogs som potentiella kandidater för att ersätta Pulis av före detta slottsförsvararen Matt Lawrence, talar på BBC Radio 5 Live.
Återstoden av Pulis coachningspersonal - inklusive Gerry Francis och Dave Kemp - har blivit ombedd av Parish att stanna kvar på resan till Arsenal innan de lämnar klubben.
Gunners chef Arsene Wenger sade: " Han har gjort ett fantastiskt arbete förra säsongen, gjort ett underverk. Jag var på ett ledningsmöte på måndag, han var där och inget tydde på att han inte skulle vara här i morgon."
Pulis ville ta större kontroll över alla fotbollsfrågor i Selhurst Park, särskilt överföringar, efter att ha missat ett antal viktiga mål.
Han och Parish var också oense om deras visioner för klubben.
Parish och sportregissören Iain Moody är ansvariga för att leverera potentiella signeringar öronmärkta av Pulis.
Moody anlände i november från Cardiff City, där han hade haft en liknande roll innan han avskedades av ägaren Vincent Tan.
Mediauppspelning stöds inte på den här enheten
Slottet signerade Liverpool full-back Martin Kelly på torsdag, medan anfallaren Fraizer Campbell anlände från Cardiff för £ 900 000 och f.d. Fulham center-back Brede Hangeland har anslutit sig till en fri.
Bara några timmar innan Pulis lämnade, Kelly berättade klubbens officiella hemsida: "Jag ser fram emot att spela under Tony och spela vanlig fotboll igen."
Hangeland valde också ut Pulis som en av sina skäl till att flytta till Selhurst Park och sade: "Allt det jag har hört om denna klubb - managern, spelarna, personalen - allt har varit bra."
Pulis lämnade Stoke förra året efter sju år på Britannia Stadium, efter att ha guidat Potteries outfit till Premier League och hållit dem där, förlänga hans rekord om att aldrig bli förvisade.
Palace var längst ner på bordet när han utsågs till Ian Holloways ersättare i november 2013.
Pulis lyckades stoppa nedgången, och en omgång av fem på varandra följande segrar från 29 Mars, med början med en 1-0 seger över Chelsea, styrde Eagles till säkerhet.
De berömda kom tillbaka från tre mål ner i de sista 11 minuterna mot Liverpool till alla utom förneka de röda titeln i slutet av förra säsongen.
Deras slutliga 11:e plats var klubbens högsta sedan 1992.
Tidigare ordförande Simon Jordan berättade Talksport att chefer "måste göra som de blir tillsagda".
"Fotboll chefer är otroligt svåra människor att ta itu med eftersom de tror sin egen hype," Jordan sade.
"Jag vet vad chefer kommer att göra, de kommer att sätta dig till svärd. Om du inte ställer dig upp och du inte hanterar din fotbollsklubb ordentligt, kommer de att köra förödelse i det och då kommer de att försvinna in i etern när det minst passar dig."
Pulis transfer spendera sedan gå Palace är cirka £10.5m - inklusive Januari signeringar Scott Dann, Jason Puncheon och Wayne Hennessey, som kom i en £3m affär från vargar, och låneavtal för Tom Ince och Joe Ledley.
I slutet av förra säsongen, Parish talade till South London Press om Pulis, säger: "Han tog en stor chans att komma till Crystal Palace på ett muntligt löfte att jag och klubben skulle stödja honom ekonomiskt."
Efter att ha styrt Palace i säkerhet sade Pulis: "Under de första veckorna hade Steve och jag våra stunder men ju längre säsongen har gått ju närmare vi har kommit.
"Vår relation, som jag tycker är den viktigaste på en fotbollsklubb, har blivit mer och mer solid."
Skrovförsvararen Curtis Davies twittrade: "Jag kan inte fatta att Pulis har gått. Han gjorde ett bra jobb på sin korta tid på Palace. Vem tror du ska ersätta honom? Malky Mackay ett bra rop?"
Chef Tony Pulis har lämnat Crystal Palace genom ömsesidig överenskommelse mindre än 48 timmar innan säsongens början.