at all." Financial difficulties meant that Crystal Palace were unable to make new signings for the 1999–2000 season and relied on youngsters such as Mullins and Clinton Morrison and veterans such as Andy Linighan as they successfully battled against relegation from the First Division. Mullins made 49 league and cup appearances in that season and a further 51 appearances in the 2000–01 season as Palace reached the semi-final of the League Cup, but narrowly escaped relegation. He was transfer listed in October 2000, due to what manager Alan Smith described as a "bad attitude", but was taken off the list and was offered and signed a new four-year contract two months later as his relationship with Smith improved. Smith said of him in January 2001, "He's a really good footballer which means I can play him in any position. I like my young players to play in different positions. This season he's played full-back, midfield and sweeper. [We've] got to work on his defending, but he's got pace, he has good vision and he wants to play football." Mullins made a total of 47 appearances in league and cup in the 2001–02 season as Palace made an ultimately unsuccessful push for the First Division play-off places. He was made captain in the 2002–03 season by manager Trevor Francis, who saw him as an integral part of the squad. He made 52 league and cup appearances as Palace advanced to the quarter-final of the League Cup, as well as recording a memorable 2–0 win over Liverpool in an FA Cup fourth round replay at Anfield. He was named Player of The Year for a second time in 2003. An offer of £600,000 from Birmingham City in January 2003 was rejected as "derisory". With one year remaining on his existing contract, Mullins turned down the offer of a new contract in May. His agent said, "It is no secret that Hayden believes he will not be able to fulfil his true potential at Palace. If the club wishes to get some financial reward for their role in his up bringing, then they need to sell him this summer." The following October, he joined West Ham United. Mullins made over 250 league and cup appearances for Palace, scoring 20 goals. West Ham United Mullins was the first signing for West Ham's newly appointed manager, Alan Pardew, and initially joined on a short-term loan