ITV commissioned The Paul O'Grady Show following O'Grady's appearance as a guest presenter for the (somewhat similar formatted) lunch-time entertainment show Today with Des and Mel (now defunct). ITV management were so impressed by his initial standing in - a last minute replacement for Des O'Connor - that he was brought back several more times to stand in for O'Connor, and subsequently O'Grady was given his own show (O'Grady also became good friends with co-presenter Melanie Sykes, who has since stood in for him on O'Grady's own show on occasion).
The series began broadcasting on ITV in October 2004, and had been greeted by ITV as the saviour of its 5–6 pm slot. The broadcaster previously had trouble filling the slot with a popular programme, with failed attempts including two daytime soap operas: Night and Day and Crossroads (the latter a revival of the soap which had been cancelled in 1988).
Guess the Tune (known as The Organ Game on the Channel 4 edition), a phone-in-competition where O'Grady plays tunes on his organ and the contestant has to guess them correctly to win up to £2000, became a popular feature of the programme. The tune that O'Grady played leading into the game was a truncated version of "Sing As We Go", by Gracie Fields. Also a stalwart of the show is O'Grady bichon frise dog, Buster, who has appeared for a full five minutes at the start of each programme since the ITV incarnation of the show.
On 10 January 2006, in a shock announcement, O'Grady said that he had decided to leave ITV for Channel 4, following a dispute between O'Grady and Granada Television (who made The Paul O'Grady Show for ITV) after Granada 'forgot' to renew O'Grady ITV contract. O'Grady was believed to have left ITV not only due to his contract renewal issues nor his salary, but rather he wanted more creative control over the show (Granada had promptly refused when the show was under their production). His own television production company, Olga TV (named after one of his pet dogs), subsequently took over production of the programme.
ITV informed O'Grady that they were unhappy with his move to Channel 4, and he became entrenched in an ongoing dispute with the broadcaster regarding the use of the same set design, props, and names.
The programme was renamed The New Paul O'Grady Show and began airing on Channel 4 in March 2006, in the same 5:00-6:00pm early evening slot, alternating in this slot every three months or so with Richard & Judy. When this new series started on Channel 4, ITV decided to air repeats of the original show in the same slot (this is partly why the Channel 4 show adopted the name The New Paul O'Grady Show). However, ITV quickly abandoned this after these repeats attracted just less than a million viewers (and was decreasing), whilst the new Channel 4 show was gaining over 3 million viewers.
The Paul O'Grady Show is broadcast live on Mondays, Tuesdays, and Wednesdays at 5:00pm. Thursday's and Friday's episode are pre-recorded on the Tuesday and Wednesday of that week, respectively, at 12:30pm (the same set-up occurred when the programme was under Granada's production).
Buster did not appear for the first two weeks due to a serious eye infection, so O'Grady's other pet dog Olga took his place instead. On 16 January 2007, viewers noticed that instead of the scheduled live show, a repeat show was aired instead. This was due to O'Grady pulling out of the show at the last minute due to illness, later discovered as a sickness bug. O'Grady returned live the next day.
Following news of premium rate phone in scandals, The Organ Game was suspended (as it relied on people calling in to enter the game). On the first episode of the new series (broadcast on 17 September 2007), Paul went over to play The Organ Game near the end of the show to find it tied up and him unable to use it. He invited viewers to telephone or e-mail Channel 4 bosses to allow him to play the phone-in game. On 22 October 2007, O'Grady announced on his show that The Organ Game would be returning; however there were only four special organ games leading up to Christmas, primarily for people who deserve the cash prize being offered (the phone line entries which used to be on the show have remained suspended). On 19 November 2007, the first of the four special Organ Game aired.
On Tuesday 15 April 2008, Melanie Sykes hosted the show, although it was not announced that she would be hosting. Sykes informed the audience that O'Grady was ill with the flu, and as such was unable to present. Sykes hosted that week's shows before O'Grady returned on Monday 21 April. However, O'Grady hadn't fully recovered, and Sykes had to be called in to do the following show on Tuesday. It was announced that Lorraine Kelly would host Wednesday's show, Brian Conley would host Thursday's show, and Shane Richie would host Friday's show. O'Grady finally returned on 28 April 2008.
In April 2008, there were two unscheduled guest-hosted weeks. O'Grady hosted the Monday show during these two weeks, but was taken ill after contracting a flu virus for the remainder of the weeks. Melanie Sykes guest-hosted five of the eight remaining shows, having previously hosted the show three times.
The show took a break on the week commencing 5 May 2008. Grand Designs Live was its 5:00pm replacement for that week, hosted by Melanie Sykes. The Paul O'Grady Show returned on Monday 12 May 2008 and continued until the series ended on Friday 13 June 2008.
Buster was originally a stray that O'Grady spotted on a motorway around ten years ago and then adopted. Buster has many fans, so much so that a limited edition Nodding Buster was made and given as a consolation prize on the show and is now given away in a tombola. Animals feature heavily on the show (mostly dogs). O'Grady also has two other dogs, called Olga (a Cairn Terrier) and Louie (short for Lucifer) and 25 other pets (giving a total of 28 pets, as said on his show when responding to a viewer's question).
A short excerpt is seen in the Doctor Who episode "The Stolen Earth" of O'Grady ranting to the audience of how many planets appeared above the sky (an allusion to the events in the episode). Ianto Jones is seen in the Torchwood Hub watching the show, commenting that it was amusing.