Madden was in his first year as a CBS analyst after retiring as coach of the Oakland Raiders. His made his CBS debut on 9/23/1979 when he called the Saints-49ers game with Frank Glieber. CBS only assigned Madden to 8 games that initial season, typically on weekends when the network had more than 6 games on its schedule. Many of his games went to rather small regional audiences. He worked primarily with Glieber in 1979, but also called one game each with Dick Stockton and Lindsey Nelson.
In 1980, CBS promoted Madden to full-time status. He worked with Gary Bender that season and was assigned to more prominent games including the NFC wild-card playoff. I specifically recall being extremely impressed with his insights while watching the Falcons-Eagles telecast that season. Madden used his coaching background to provide great perspective which was a stark contrast to the typical lackluster analysis of that era. He paid extra attention to blocking and interior line play and received many positive media reviews for his football commentary. Outside of the booth, his popularity was skyrocketing from the Miller Lite beer commercials. Madden had also developed a fear of flying so he travelled to games by train.
Heading into the 1981 season, CBS decided to break up the Summerall/Brookshier team and elevate Madden to the role of #1 analyst. During the first half of that season, CBS experimented by pairing Madden with Vin Scully for 4 weeks and then with Summerall for 4 weeks to determine which play-by-play partner meshed best with Madden. At mid-season, CBS chose to permanently pair Pat and John together. The Summerall/Madden team remained intact through the 2001 season (including a move to FOX in 1994) and would call 8 Super Bowls.