Besökarna kom bakifrån efter att Romelu Lukaku sköt in för att belöna Everton för deras tidiga dominans.
Palace utjämnade genom en Mile Jedinak straff på 30 minuter innan Fraizer Campbell huvud och Yannick Bolasie låg skott sätta dem ordentligt i kontroll.
Mediauppspelning stöds inte på den här enheten
En Leighton Baines straff gav Everton hopp sent men Palace höll på.
Detta är en mindre modig och djärv Palace till den som leds av Tony Pulis som fick en imponerande 3-2 seger på denna mark i slutet av förra säsongen men de förblir fysiskt konkurrenskraftiga och taktiskt skarp under den erfarna Neil Warnock, som nu har en seger att gå med de två dragningar som han började sin andra trollformel som chef för klubben.
Denna seger är ett bevis på deras motståndskraft och självförtroende eftersom de knappt var med i matchen under de första 30 minuterna mot en Everton-sida som inte visade några initiala illdåd från sina Europaliga ansträngningar mot Wolfsburg på torsdag.
Den första bouyancy från Toffees var möjliggörs av de färska benen Christian Atsu, Samuel Eto'o och Leon Osman, som alla var att göra sin första början av säsongen och som alla ställde Palace problem.
Det var från den senares prydliga pass att hemmasidan tog ledningen, som Lukaku samlade innehav och drev förbi en statisk back-line innan sidfoten ett lågt skott förbi Julian Speroni.
Det var alldeles för lätt för Toffees, så mycket att de tog sin fot av gasen och var ogjort av sin egen hybris som Palace utjämnade helt mot en run of play som hade, i sanning, marken till ett nära stopp.
John Stones och Sylvain Distin lämnade ett huvud flick-on för väktare Tim Howard, som kom för sent för att göra anspråk på bollen och istället tog ut James McArthur i lådan, vilket ger Jedinak chansen att slå i en ostoppbar straff.
Mediauppspelning stöds inte på den här enheten
Målet gav Palace en tum och därifrån tog de en kilometer.
Warnock män kom inom inches av att ge sig själva en halv tid bly som Bolasie avböjde 30-yard skott slog hörnet av målramen.
Men de behövde bara vänta till nio minuter in i den andra halvan, som Howards upptrappade eftermiddag fortsatte när hans felbedömda klaff på ett kors tillät Campbell att gå hem och sätta Palace framför.
Med Everton i disarray, besökarna utökade sin ledning som Jason Puncheon hittade Bolasie i lådan och han slog en låg skott över Howard och in i nätet på 69 minuter.
Introduktionen av Steven Naismith och Kevin Mirallas gav hemsidesimpulsen, vilket resulterade i att James McCarthy drog en foul från Scott Dann för att vinna ett straff.
Baines skickade 83:e minuten spot kick för att dra en tillbaka men Everton kunde inte hitta en equalizer trots sex minuter av tillagd tid.
Everton manager Roberto Martinez:
" Straffet var en otrolig belöning för Palace och sedan på den mentala förändring tillät Palace att ha en hel del tro och att ändra spelet.
"Det var mycket okaraktäristiskt av oss att erkänna tre mål med tre fel, men även då karaktären var otrolig och vi nästan lyckats få något ur spelet."
Crystal Palace chefen Neil Warnock:
"Detta ger alla en hel del tro. Vi borde ha vunnit de andra två matcherna mot Newcastle och Burnley och vi var besvikna över att inte göra det.
"Jag tyckte vi förtjänade att vinna den idag. Vi var oroliga under de första 20 minuterna och gav dem lite för mycket respekt men från det ögonblicket växte vi in i spelet och vi sa att det var ett spel vi kunde fortsätta och försöka vinna.
"Det som gladde mig var att Everton är en bra sida och vi var tvungna att hänga där ibland och sätta huvudet i och göra tacklingar och block, och jag gillar den typen av fotboll."
Matchen slutar, Everton 2, Crystal Palace 3.
Andra halvlek, Everton 2, Crystal Palace 3.
Offside, Everton. Gareth Barry försöker en genom boll, men Romelu Lukaku fångas offside.
Försök missade. Adlène Guédioura (Crystal Palace) höger fotade skott från höger sida av lådan missar till vänster. Hjälpt av Mile Jedinak efter en snabb paus.
Foul av Phil Jagielka (Everton).
Kevin Doyle (Crystal Palace) vinner en frispark i den defensiva halvan.
Steven Naismith (Everton) vinner en frispark i den defensiva halvan.
Foul av Kevin Doyle (Crystal Palace).
Foul av Steven Naismith (Everton).
Joe Ledley (Crystal Palace) vinner en frispark på vänsterkanten.
Romalu Lukaku (Everton) vinner en frispark på vänsterflygeln.
Foul av Adlène Guédioura (Crystal Palace).
Julian Speroni (Crystal Palace) visas det gula kortet.
Försök missade. Romelu Lukaku (Everton) vänster fotade skott från mitten av lådan är för hög. Hjälpt av Kevin Mirallas.
Substitution, Crystal Palace. Ezekiel Fryers ersätter Yannick Bolasie.
Substitution, Crystal Palace. Kevin Doyle ersätter Fraizer Campbell.
Försök missade. Phil Jagielka (Everton) höger fotade skott från vänster sida av lådan är nära, men missar till vänster. Hjälpt av Leighton Baines.
Hörnet, Everton. Förföljd av Jason Puncheon.
Substitution, Everton. Darron Gibson ersätter Sylvain Distin.
Substitution, Crystal Palace. Adlène Guédioura ersätter James McArthur.
Mål!  Everton 2, Crystal Palace 3. Leighton Baines (Everton) konverterar straffet med en vänster fotad skott till nedre vänstra hörnet.
Straffet Everton. James McCarthy drar ett brott i straffområdet.
Straff som medgavs av Scott Dann (Crystal Palace) efter ett brott i straffområdet.
Phil Jagielka (Everton) vinner en frispark i defensiva halvan.
Foul av Fraizer Campbell (Crystal Palace).
Försening över. De är redo att fortsätta.
Försening i match Damien Delaney (Crystal Palace) på grund av en skada.
Hörnet, Everton. Förföljd av Mile Jedinak.
Försök blockerat. Romelu Lukaku (Everton) vänster fotade skott utanför lådan är blockerad. Hjälpt av Kevin Mirallas.
Steven Naismith (Everton) visas det gula kortet för en dålig foul.
Foul av Steven Naismith (Everton).
Mile Jedinak (Crystal Palace) vinner en frispark i defensiva halvan.
Jason Puncheon (Crystal Palace) visas det gula kortet.
Leighton Baines (Everton) vinner en frispark i den defensiva halvan.
Foul av Jason Puncheon (Crystal Palace).
Steven Naismith (Everton) vinner en frispark i den defensiva halvan.
Foul av Fraizer Campbell (Crystal Palace).
Försöket räddades. Leon Osman (Everton) vänster fotade skott från utsidan rutan sparas i nedre vänstra hörnet. Hjälpt av Leighton Baines.
Hörnet, Everton. Förföljd av Scott Dann.
Offside, Everton. Leon Osman försöker en genom boll, men Kevin Mirallas fångas offside.
Crystal Palace hävdade sin första seger för säsongen när de förlängde Evertons segerlösa ligan strimma på Goodison Park till fyra matcher.