วงดนตรีได้เข้าร่วมการแข่งขันรอบชิงชนะเลิศระดับรัฐเวสเทิร์นออสเตรเลียของการประกวดวงดนตรีระดับมหาวิทยาลัยแห่งชาติออสเตรเลียณไนต์คลับแพลเน็ตในนอร์ทเพิร์ธ เมื่อปี 1997 วง Eskimo Joeชนะเลิศและได้ไปแข่งขันต่อในรอบชิงชนะเลิศระดับประเทศ ในขณะที่วง Red Jezebel ได้อันดับที่สี่

ชื่อวงดนตรีมาจากรหัสลับสำหรับการอพยพฉุกเฉินที่ใช้โดยเครือซูเปอร์มาร์เก็ตแห่งหนึ่งในออสเตรเลีย ซึ่งสมาชิกหลายคนในวงเคยทำงานที่นั่นในช่วงแรกๆ ของวง

ระหว่างปี 1998 ถึง 2000 วงดนตรีได้ปล่อยอีพี ออกมาสามชุด ได้แก่Joyful Possibilities , In TransitและIntermezzoในช่วงเวลานั้น วงดนตรีได้รับรางวัล "Kiss My WAMi " สาขา "วงดนตรีที่มีอนาคตไกลที่สุด" ในปี 1998 ได้ทำการทัวร์คอนเสิร์ตระดับประเทศสองครั้ง (ร่วมกับJebediahและBodyjar ) ได้ขึ้นแสดงสดใน รายการวิทยุ Triple Jและ รายการ Recoveryทางช่อง ABC และได้แสดงในงานThe Big Day Outด้วย

ในปี 2002 Red Jezebel ได้ออก EP ชื่อ Home Comingและในปีเดียวกันนั้น Mark Cruickshank ก็ได้รับรางวัล WAMi สาขา "นักเล่นเบสชายยอดนิยม" ^{[ 1 ]}

ในเดือนตุลาคมปี 2003 วง Red Jezebel ได้ปล่อยซิงเกิล "Wide Open Spaces" ซึ่งได้รับความนิยมและเปิดออกอากาศอย่างแพร่หลายในออสเตรเลีย

Revelationsเป็นอัลบั้มสตูดิโอชุดแรกของวง และวางจำหน่ายในเดือนมิถุนายน ปี 2006 โดยค่ายเพลง Sunday Ride Records ในเมืองเพิร์ธ บันทึกเสียงโดยเดฟ พาร์กิน ที่ Blackbird Studios ในรัฐเวสเทิร์นออสเตรเลีย อัลบั้มนี้ประกอบด้วยเพลง "Wide Open Spaces", "Ocean Blue Eyes", "Devil's Advocate", "You're Making Me Nervous" และ "See Through Dress" ซึ่งได้รับความนิยมอย่างมากในสถานีวิทยุ Triple J

วง Red Jezebel ใช้เวลาตลอดเดือนกรกฎาคม พ.ศ. 2549 ใน Blackbird Studios เพื่อทำการปรับแต่งขั้นสุดท้ายให้กับ EP อีกชุดหนึ่งซึ่งมีกำหนดวางจำหน่ายในเดือนกรกฎาคม พ.ศ. 2550 โดยตั้งใจให้เป็นผลงานภายใต้ค่ายเพลงใหญ่ครั้งแรกของวง หลังจากเซ็นสัญญากับ ค่าย Mushroom Recordsผ่านทาง Warner Music แผนการวางจำหน่าย EP ครั้งแรกนี้ล่าช้าออกไปเนื่องจากปัจจัยต่างๆ ที่เกี่ยวข้องกับบริษัทแผ่นเสียง ทำให้วงต้องออกจาก Warner Music ^{[ 2 ]}แทนที่จะเป็นเช่นนั้น วงจึงได้วางจำหน่ายอัลบั้ม LP 13 เพลงชื่อHow I Learnt to Stop Worryingในเดือนตุลาคม พ.ศ. 2550 ภายใต้ค่ายเพลงของตนเอง Sunday Ride Records ซึ่งจัดจำหน่ายโดยMGMเพลงแรกจากอัลบั้ม "Kicking Deadly Sins" ได้รับการออกอากาศอย่างกว้างขวางใน Triple J ^{[ 3 ]}สถานีวิทยุชุมชนต่างๆ ทั่วออสเตรเลีย (Edge Radio ^{[ 4 ]} RTRFM ^{[ 5 ]} ) และมิวสิ กวิดีโอก็ได้รับความนิยมอย่างมาก^{[ 6 ]}

• พอล วูด – นักร้องนำ, กีตาร์
• เดฟ พาร์กิน – กีตาร์
• มาร์ค ครูอิคแชงค์ – กีตาร์เบส
• อเล็กซ์ ไฮแมน – กลอง
• เฟรเซอร์ คริงเกิล – กลองชุด
• คริส เฮย์ส – กีตาร์

รางวัลอุตสาหกรรมดนตรีแห่งรัฐเวสเทิร์นออสเตรเลีย (หรือที่รู้จักกันทั่วไปว่า WAMis) เป็นรางวัลประจำปีที่มอบให้แก่อุตสาหกรรมดนตรีร่วมสมัยในท้องถิ่น จัดโดยสมาคมอุตสาหกรรมดนตรีแห่งรัฐเวสเทิร์นออสเตรเลีย (Western Australian Music Industry Association Inc หรือ WAM)