Allardyce left in October 1999 to join his old team Bolton Wanderers. In September 2003, Notts County faced the real possibility of dissolution. Crippling debts and an increasingly impatient Football League board combined to leave the future of the league's oldest club in doubt. However, the considerable efforts of a group of local businessmen and the club's supporters helped save the club from extinction. But despite new ownership, the club were unable to avoid relegation back to the bottom division in 2004. In a similar circumstance as their relegation in 1992, due to the rebranding of the Football League, County went from Division Two to League Two.
Ian Richardson replaced Gary Mills as manager in November 2004. Richardson managed to guide the club away from the relegation zone and held the manager's job until the end of the season when Gudjon Thordarson became the club's sixth manager in five years. The 2005–06 season began well for the Magpies: they won or drew their first seven league games and were top of the table in September. But their form dropped and they escaped relegation only on the final day of the season with a 2–2 draw against Bury, whilst Oxford United lost and went down. The Magpies' 21st place in League Two, and 89th place overall, was the lowest position the club had ever finished, and at the end of the season both the chairman and the manager left, a long-standing youth squad programme was ended, and many of the first-team players were out-of-contract or nearing contract maturity.
Former assistant manager Steve Thompson was appointed as manager and he led the team to a 13th place division finish in 2006–07. The following season started with poor results, including early exits from the League Cup and the Football League Trophy, and Thompson was sacked in October 2007, to be replaced by Ian 'Charlie' McParland. However, the team's poor form continued and safety from relegation was only secured in the penultimate match of the season. McParland parted company with the club in October 2009 with Notts fifth in League Two and 4 points from the top of the table; youth team manager Michael Johnson and Assistant Manager Dave Kevan were installed as joint caretaker managers.
In June 2009, it was announced that County were in talks on a takeover by Munto Finance, a Middle Eastern consortium owned by Qadbak Investments and represented by Nathan and Peter Willett. Speculated by the British media and supported in part by various press releases, the club were believed to be given multi-million pound backing and were linked during the takeover's initial planning stages with the Qatari royal family by British tabloids; however, the latter claim was denied by the family. The Supporters' Trust, who owned the majority 60% share in the club, voted in favour of the takeover. On 14 July 2009, the takeover was confirmed, with Peter Trembling being appointed as Executive Chairman. A week later former England manager Sven-Göran Eriksson was announced as the club's new Director of Football, having been persuaded by convicted fraudster Russell King to join Notts County. On 28 July 2009, the club unveiled a new logo.
On 20 October 2009, the League announced that County's owners had met its "fit and proper persons" regulations, and that while their structure was "complicated" and featured "both offshore entities and discretionary trusts", it had provided "extensive disclosure" to the League on their ownership structure. The League also stated that public disclosure of their ownership structure was a "matter for the club". On 27 November 2009,The Guardian revealed that the league reopened its inquiries into the ownership of Notts County. The League chairman, Brian Mawhinney, confirmed the club has been sent a series of questions relating to its ownership structure.
On 12 December 2009 Peter Trembling purchased the club for a nominal fee from Munto Finance.