Al comienzo, sus miembros se inspiraron en bandas de skate punk como NOFX y Propagandhi, pero después de la publicación de The Rest is Silence (1996) y la salida del bajista Patrik Trydvall, adoptaron un sonido que recuerda a Thin Lizzy, The Misfits y Ramones, talmente una fusión de garage punk y pop punk. Su siguiente álbum, You Can't Keep a Good Band Down (1998), recibió la atención de Maximum Rocknroll que lo elogió como «el mejor CD punk melódico desde el No Control de Bad Religion».^[4]​^[5]​

Randy firmó con Burning Heart Records, una subseello de Epitaph Records, a principios de los años 2000. El 2002, Randy fue invitado a actuar al Club Debaser de Estocolmo para homenajear Joe Strummer de The Clash, junto con otras bandas.^[6]​

Su último álbum, Randy the Band, fue publicado el enero de 2006 por Burning Heart y Fat Wreck Chords. El julio de 2020, la canción «The Exorcist», incluida a You Can't Keep a Good Band Down, apareció al podcast insignia de la BBC, Kermode & Mayo's Film Review.^[7]​

A lo largo de los años, Randy ha logrado cierta consideración de culto entre la comunidad punk internacional y ha tenido un éxito particular en su país natal. Es un grupo conocido para escribir canciones pegajosas con mensajes políticos, a menudo abordando temas como la desigualdad social, lo socialismo y las revoluciones de la clase trabajadora a lo largo de la historia europea.^[8]​^[9]​^[10]​

• There's No Way We're Gonna Fit In (Dolores Records, 1994)
• The Rest Is Silence (Dolores Records, 1996)
• You Can't Keep a Good Band Down (Ampersand Records, 1998)
• The Human Atom Bombs (Burning Heart, 2001)
• Welfare Problems (Burning Heart, 2003)
• Randy the Band (Ny Våg/Burning Heart/Fat Wreck Chords, 2005)

• "En Riktig Man?" (1992)
• No Carrots for the Rehabilitated EP (1993, Dolores Records)
• Ska EP (1994, Dolores Records)
• "Education for unemployment" (1995, Dolores Records)
• Refused Loves Randy EP (1995, Startrec, con Refused)
• "At Any Cost" (1996, Dolores Records)
• Out of Nothing comes nothing 7" (1998, Ampersand Records)
• Return of the Read Menace (1999, G7 Welcoming Committee Records)
• "I Don't Need Love" (2001, Burning Heart)
• Cheater EP (2001, Busted Heads Records/G7 Welcoming Committee)
• "The Heebie Jeebies" (2001, Burning Heart)
• "Fat Club" (2001)
• Dropping Food on Their Heads Is Not Enough: Benefit for RAWA (2002, Geykido Comet Records)
• "X-Ray Eyes" (2003, Burning Heart)
• "Beware (If You Don't Want Your Babies To Grow Up To Be Punk Rockers)" (2004, Fat Wreck Chords, amb Fat Mike)
• Chemical X DVD (2008, Geykido Comet Records)