After six months of negotiations, Leeds were this week bought by GFH Capital, and manager Neil Warnock, having said anyone could have done his job for the first four cash-strapped months of the season, claimed this match marked the first day of his pursuit of a record-setting eighth promotion.
And, although the goals scored by Luciano Becchio and Paul Green do not mask the fact Leeds had gone seven without a win prior to meeting Palace, leaving them far from Premier League material, this was as good a start as they and GFH could have wished for.
Equally, a first defeat since their Capital One Cup defeat to Preston on August 28 does not spell disaster for Palace, although Cardiff's win at Barnsley means top spot is no longer theirs.
Early on, Leeds fed off new loanee Jerome Thomas' energy and soon Becchio was denied by Julian Speroni in the Palace goal, before the Argentinian stopper, a summer target of Warnock, did brilliantly to get down low and keep out David Norris after a bursting run from the midfielder.
Paddy Kenny was then called into action at the other end, getting the slightest touch to an across-goal drive from Wilfried Zaha, who outmuscled Sam Byram to get a shot in.
He then got to work behind a routine drive from Owen Garvan, before a brilliant double save kept his side level. First he flung himself to his left to palm away Jonathan Parr's curler, leaving the goal open in the process. He was up quickly, though, shutting down Glenn Murray who looked a safe bet to grab his 16th of the season from six yards.
Zaha was Palace's most dangerous player - far too strong for opposite number Byram - and the two were involved in a flashpoint on the stroke of half-time, with the former not getting the penalty he courted after appearing to be tripped. Fortunately for him, he received no caution for his subsequent shoving of Norris.
There was no doubt Palace had ended the first half the better but seven minutes into the second half, they were behind, owing largely to Peter Ramage's failure to clear his lines. After Lee Peltier's cross was nodded across goal by Green, the experienced defender headed it against his own man, Mile Jedinak, allowing Becchio to pounce from two yards.
Palace's attempts at a response inevitably went through Zaha who again thought he had claims on a penalty when he and Byram became entangled for a second time, although the best chances fell in Leeds' favour, with Norris drilling over after a Byram cross fell kindly for him.
A second Leeds goal would arrive, though, with Green's 75th-minute sweet back-post volley - after Alan Tate's punt forward fell to him - deflecting beyond Speroni's reach.
Thinking the game was done, Warnock sent on Ross McCormack for a first home appearance in almost three months following injury, but Leeds were given a reality check with five minutes left when Ramage dived to head in Kagisho Dikgacoi's cross.
With five minutes of time added on, Palace had a chance to get a second, but the closest they came was Michael Tonge booting off his own line following a scramble, and Leeds held on.