Attracted by the success of "Smokey Joe's Cafe" with Gardner on lead vocal, Atlantic Records signed an independent producer-composer contract with Leiber & Stoller. Two hand-chosen Californians, Billy Guy and Leon Hughes, completed the original Coasters line-up. They were contracted to Atlantic's new subsidiary, Atco Records. Through the Coasters, Leiber-Stoller launched some of the most entertaining songs of the '50s. The first Coasters' recording was "Down In Mexico" on January 11, 1956. The record became a sleeper R&B hit, followed by the minor Pop hit, "One Kiss Led To Another" (#73). The group now hit the road for national promotion and produced R&B's most famous double-sided smash in 1957. "Young Blood" (the original A-side) was an R&B Juke Box #1 hit, and a #2 hit on the R&B Disc Jockey chart, while the flip side, "Searchin'", which occupied the #1 spot on the R&B Best Seller chart for thirteen weeks, and lasted at #1 on the R&B Disc Jockey chart for seven weeks. Both titles also became national Top Ten hits, staying on the Billboard charts for half a year.

After three less successful releases, The Coasters reformed and moved from the West Coast to New York. Bobby Nunn and Leon Hughes stayed in California, where Nunn later launched his own The Coasters, Mark II. Nunn died of heart failure on November 5, 1986 in Los Angeles. His group, now led by Billy Richards Jr, continued to tour as Billy Richards' Coasters. Hughes also started his own Coasters tribute group, The Original Coasters.

Tenor, Cornell Gunter and bass, Will "Dub" Jones, replaced Hughes and Nunn, and in 1959, The Coasters rattled off a string of hits that included "Yakety Yak" (a #1 Pop hit in 1958), "Charlie Brown" (#2 in 1959) and "Along Came Jones" (#9 in 1959) and the double-sider "Poison Ivy" (#7) b/w "I'm A Hog For You" (#38). The classic Coasters had a fifth member in guitarist Adolph Jacobs from Oakland, California, who was succeeded by a Coasters' employee, Sonny Forriest, on "What About Us" (#44), which was the last single of the highly successful year of 1959.

The productions of the Coasters' Atco recordings were far superior to any contemporary group efforts, using the best musicians available, especially King Curtis' sax breaks, and with the lyrics neatly deriding aspects of teenage and/or Black ghetto life. The group also worked out hilarious stage routines and became the most professional act in late '50s Rhythm & Blues and early '60s International Pop.

In 1960, the Coasters had a few more minor hits with "Run Red Run" (#36), "Besame Mucho" (#89), "Wake Me, Shake Me" (#87) and "Shoppin' For Clothes" (#99). In 1961 they hit with "Wait A Minute" (#37), which had actually been recorded in 1957. After the group's last U.S. Pop Top 30 entry, "Little Egypt" (#23), Cornell Gunter left the group in June, 1961. He formed his own Fabulous Coasters a couple of years later.

Leiber-Stoller had left Atco/Atlantic in 1963, and the hits quickly dried up, but the vocal quartet renewed their collaboration with the team in late 1966, recording for the CBS subsidiary Date Records. By this time however, Doo-Wop music was hopelessly out of style, and despite releasing several new records, The Coasters were unable to repeat their earlier success. The group continued to perform all over the United States and toured Europe several times. They even made a brief come-back in 1972 with a re-rendition of "Love Potion Number Nine" which reached #6 in Canada. By the early '80s, Carroll had left to reform The Cadillacs, and Guy and Jones sporadically acted with a special World Famous Coasters in California. In the late '90s yet another version of the group, Billy Guy's Coasters, emerged on the scene, semi-coached by Billy Guy.

In 1987 The Coasters, Gardner, Guy, Jones, and Gunter (the line-up that made the hits) were inducted into the Rock and Roll Hall of Fame, the first vocal group receiving that honor. Carl Gardner & The Coasters were, despite competition from bogus and off-spring Coasters groups, heavily engaged in live bookings during the late '80s and the whole of the '90s, even performing at the Carnegie Hall. All of the early members launched their off-shoot Coasters' recording groups during later years. Billy Guy issued records as Billy Guy & The Coasters, and there were Bobby Nunn's Coasters, Mark II, later touring as Billy Richards West Coasters; Leon Hughes' Original Coasters; Cornell Gunter's Fabulous Coasters (acting with replacement members as Cornell Gunter's Coasters Inc). There also was Will Jones' World Famous Coasters, which often featured Billy Guy. The true Coasters though, were led by Carl Gardner. Carl Gardner Jr., took over as lead singer when his father retired in 2005. In late June, 2007, Carl Gardner's autobiography Carl Gardner: Yakety Yak I Fought Back - My Life with The Coasters was published by AuthorHouse. The Coasters' recordings produced by Leiber and Stoller for Date/King (1966-1972) were released on the CD "Down Home" by Varese Vintage in 2007. The complete Atco recordings (1954-1966) were released in a four-CD set, "There's a Riot Goin' On: The Coasters on Atco", by Rhino, also in 2007

Tragedy has struck The Coasters several times. Saxophonist and fifth Coaster King Curtis was stabbed to death by two junkies outside his apartment building in 1971. Cornelius Gunter was shot to death while sitting in a Las Vegas parking garage in January, 1990. Nate Wilson, a member of one of Gunter's offshoot Coasters groups, was shot and his body dismembered in 1980. Former manager Patrick Cavanaugh was convicted of murder and died in 2006 in Nevada's Ely State Prison at the age of 60. Carl Gardner passed away on June 12th, 2011 at the age of 83 following a long bout with congestive heart failure and vascular dementia.

A version of The Coasters continued to appear regularly on oldies shows and PBS specials.

The Coaster's Top Ten Hits

1957 - Young Blood - #8
1957 - Searching- #3
1957 - Poison Ivy - #7
1958 - Yakety Yak - #1
1959 - Charlie Brown - #2
1959 - Along Came Jones - #9

Be sure to read Gary James' Interview With The Coasters' Carl Gardner