The Dead Kennedys formed in June 1978. In 1980, one of their songs called "California Über Alles" became popular in the punk music scene. In 1980, they recorded and released a song called "Holiday in Cambodia". That same year, they made their first album, "Fresh Fruit for Rotting Vegetables". In the early 1980s, the band toured all over the United States, Europe, and Australia.