Группа была основана в 1992 году в городе Де-Мойне, штат Айова, Кори Тэйлором и Джоелом Экманом. В скором времени к ним присоединился друг Кори — Шон Экономаки. Однако, вместо того чтобы заниматься написанием песен, группа играла в клубах, постоянно меняя гитаристов, некоторых даже после одного шоу. В 1995 году в группу на место постоянного ведущего гитариста приходит Джеймс Рут. Группа приступила к созданию первых демозаписей, но в 1997 году Кори Тейлор и Джеймс Рут присоединяются к Slipknot, Джоел заводит семью, а Шон становится концертным менеджером. Stone Sour формально прекращают своё существование, однако в 2000 году старый друг Кори, Джош Рэнд продемонстрировал ему свои песни. Рэнд начал работать над ранними версиями песен «Get Inside», «Orchids», «Idle Hands», которые в дальнейшем вошли в первый альбом группы. Джош и Кори стали работать вместе. После полутора лет совместной работы, было решено собрать прежний состав группы.
Коллектив дебютировал в начале 2002 года, когда композиция «Bother» прозвучала в саундтреке к фильму «Spiderman». А затем, в том же году 23 августа в свет вышел и первый, одноименный альбом команды — Stone Sour. Диск дебютировал на 46 месте в Billboard Top 200, и за первую неделю продаж тиражом проданных копий составил 25 тысяч. Спустя год альбом стал «золотым», а его тираж достиг полумиллиона экземпляров. Синглы «Get Inside» и «Inhale» были номинированы на премию Грэми в 2003 и 2004 году соответственно. Группа отправилась в турне и выступала на таких фестивалях как Rock am Ring, Download и других. В сентябре 2003 лейбл переиздает дебютный альбом группы, добавив 5 бонус-треков и DVD-диск с клипами. В связи с записью третьего студийного альбома Slipknot и последующего после него тура, Джим и Кори временно уходят из группы, а остальные участники начинают готовить материал для последующего альбома.
В декабре 2005 года группа приступают к написанию песен для нового альбома, получившего название Come What(ever) May. Продюсером был выбран Ник Рискулинеш. В это время группу покидает Джоэл Экман, из-за болезни и последующей смерти своего сына, у которого обнаруживается рак мозга.
На место Джоела пришел бразилец Рой Майорга (ex-Soulfly, ex-Sepultura), которому очень понравился первый альбом группы.
В апреле выходит первый клип и песня с нового альбома - «Hell & Consequences», а 23 мая официально выходит новый сингл: «30/30-150», который был записан при участии ударника Godsmack. Ещё позже в сеть были выложены песни «Reborn», «Through Glass» и Come What(ever) May. 1 августа альбом появляется в продаже и практически сразу попадает в первую 5-ку Billboard.
В сентябре группа отправляется в масштабное турне, во время которого музыканты посетили и Россию. 17 октября 2006 года в Москве, в магазине Союз, состоялась пресс-конференция группы, а 18 октября они выступили с концертом в Лужниках в рамках премии RAMP 2006. 26 июня 2007 года состоялся релиз специального издания Come What(ever) May, который содержал в себе выступление на RAMP, клипы «30/30-150», «Through Glass», «Sillyworld», «Made of Scars» и 6 песен, не вошедших в первое издание альбома.
В феврале 2010 года группа приступила к записи нового альбома. На роль продюсера группа планировала привлечь Роба Кавальо, но в итоге продюсером нового альбома, получившего название Audio Secrecy, стал Ник Раскулинеш. Audio Secrecy вышел 7 сентября на лейбле Roadrunner. В поддержку альбома группа выпустила синглы «Mission Statement»,«Say You’ll Haunt Me», «Digital (Did You Tell)» и «Hesitate». В это же время группа записывает концертный DVD Live at Brighton.
В апреле 2011 года в середине «Avalanche Tour» Stone Sour покинул Шон Экономаки, «чтобы разобраться с личными проблемами». Его временно заменил Джейсон Кристрофер, участник турового состава группы Sebastian Bach. 4 мая на сайте группы появилось объявление, сообщающее о том, что Шон окончательно покинул состав Stone Sour.
20 марта 2011 года Кори Тэйлор на своей личной странице в твитере объявил о том что группа в скором времени начнет работать над своим четвертым альбомом. Позднее стало известно что это будет концептуальный альбом и что он будет состоять из двух частей, по мотивам которых выйдет серия комиксов. 3 мая Джеймс Рут сообщил о том что на время записи нового альбома к группе присоединяется Рэйчел Болан (Skid Row). 27 марта 2012 года группа приступает к записи первой части House of Gold and Bones в студии Sound Farm около Де-Мойна. В этот же день на официальной странице группы в Facebook, появилась песня «The Pessimist», доступная для свободного скачивания. 24 августа 2012 года выходит двойной сингл «Gone Sovereign/Absolute Zero», а затем 12 октября и сам House of Gold and Bones Part 1. 12 февраля вышел сингл «Do Me a Favor» со второй части альбома, выход которой назначен на 8 апреля 2013 года. 3 апреля альбом House of Gold and Bones Part 2 стал доступен для свободного прослушивания на сайте группы.
23 октября 2012 года Джош Рэнд на официальной странице Stone Sour на Facebook сообщил, что Джонни Чоу будет играть на басу в последующем турне в поддержку альбомов.
В феврале 2014 Джеймс Рут не смог принимать участие в зимнем турне группы, поскольку он решил сосредоточить свои силы на будущем альбоме Slipknot. 17 мая 2014 года на аккаунте гитариста в Instagram фанат спросил Джеймса, сможет ли он принять участие в летнем турне группы по США 18-20 июля. Рут ответил: «Я больше не в этой группе. Это не моё решение. Я не счастлив насчёт этого». 18 мая 2014 года группа на официальной странице Facebook подтвердила уход гитариста: « Некоторые из вас, возможно, слышали на данный момент, что Stone Sour и Джеймс Рут расстались. Мы хотели подождать до завершения нового альбома Slipknot, но в свете последних событий, мы собираемся подтвердить эту информацию и двигаться дальше. Мы считаем, что это будет лучше для обеих групп и надеемся, что это отразится в грядущие дни».
5 октября 2014 года на странице Stone Sour в Facebook было сообщено о начале записи нового EP, получившего название Meanwhile in Burbank и вышедшего в 2015 году. Позднее Тейлор прокомментировал EP: "Это то, что мы хотели сделать еще с момента основания. Мы всегда хотели этого. Люди приходят и уходят и раньше мы просто не имели возможности. Тогда мы говорили: "Ну, черт с этим".
В феврале 2015 года, Stone Sour выпустили кавер-версию и видеоклип на композицию группы Metal Church, "The Dark"., а 18 апреля состоялся релиз самого EP. Также Кори Тейлор анонсировал еще две части, под названием Straight Outta Burbank и No Sleep Till Burbank. Straight Outta Burbank.. вышел в ноябре того же года.
26 июля 2016 года Тейлор в интервью Billboard.com сообщил, что группа занимается подготовкой демо-версий песен для будущего альбома, запись которого начнется в 2017 году.
23 января 2017 года Кори Тейлор официально подтвердил начало записи нового альбома под названием Hydrograd. Также он сообщил что в музыкальном плане альбом будет сочетать элементы звучания предыдущих альбомов группы с элементами хард-рока и панк-музыки. 27 апреля 2017 года группа выпустила Fabuless, первый сингл с будущего альбома, а также сообщила трек-лист и дату релиза.
