Відомий продюсер запропонував музикантам поджемувати разом з колишнім головою "Soundgarden" Крісом Корнеллом і подивитися, що з цього вийде. Вийшло дуже навіть нічого, і утворився квартет у травні 2001 року приступив до студійної роботи.
Протягом місяця група записала 21 пісню, але потім процес застопорився. Як пізніше пояснили музиканти, у всьому винні були менеджери, що надавали на них зайвий тиск. Справа закінчилася тим, що в квітні 2002-го Корнелл грюкнув дверима, а запланований виступ команди на "Оззфесте" довелося відмінити.
Втім, "розлучення" тривав недовго, і після того як колектив уклав договір з новою менеджерською компанією "The Firm", всі розбіжності були улагоджені, а Кріс повернувся на своє місце. Група тепер отримала назву "Audioslave," і в серпні 2002-го під цим ім'ям вийшов перший сингл, "Cochise", з піснею присвяченої легендарному індіанському вождю. Через два місяці фірма "Epic Records" випустила дебютну повнометражку. Альбом досить швидко досяг платинової позначки, проте викликав при цьому суперечливі відгуки. Одні критики представляли групу як збіговисько багатеньких музикантів, вічно собачащіхся один з одним з приводу саунд-продюса, а інші порівнювали "Audioslave" з "Led Zeppelin" і говорили про внесення ними в сучасний мейнстрім так відсутнього духу 70-х.
Як би там не було, але коли команда вирушила у світове турне, відгуки на її живі виступи були завжди позитивними. Концертна популярність "Audioslave" виявилася настільки велика, що під час туру "Lollapalooza" колектив затьмарив хедлайнерів "Jane s Addiction".
Після року напружених гастролей послідувала перепочинок, і потім почалася робота над новими піснями. Навесні 2005-го команда провела обкатку свіжого матеріалу в невеликому клубному турі, які пройшли зі свідомо аншлагами. Трохи пізніше "Audioslave" стали першою американської рок-бандою, відігравши концерт на Кубі (аудиторія склала близько 70000 глядачів). Настільки історичну подію було відзнято на відео і в жовтні 2005-го випущено у форматі DVD. 24 травня цього ж року вийшов другий альбом, "Out of Exile". Диск дебютував на першій позиції в чартах "Billboard", а сингли "Be Yourself", "Your Time Has Come" і "Doesn t Remind Me" тут же зазвучали в ефірі американських радіостанцій. За останній з цих пісень "Audioslave" згодом були номіновані на "Греммі" в категорії "Best Hard Rock Performance".
Восени 2005-го музиканти зробили своє перше північноамериканське турне в ролі хедлайнерів, а в 2006-му під керівництвом продюсера Брендана Про Брайана вирушили готувати третій альбом з робочою назвою "Revelations".