Родился в Одессе в семье Михаила Иосифовича и Надежды Аркадьевны Костюшкиных. Через год семья переехала в Ленинград. Отец был джазовым саксофонистом, мать – в прошлом известная питерская манекенщица. С 14 лет начал заниматься дзюдо, затем восточными единоборствами. Окончил музыкальную школу. В свое время Стасу прочили большую оперную карьеру. В музыкальной школе педагоги отмечали его голос — солировал в хоре. Но тогда он мечтал о карьере драматического артиста и, получив аттестат, понес его в ЛГИТМиК. Но по пути в вуз встретил знакомую девочку из музыкалки, и она уговорила его показаться педагогу из консерватории, где преподавала ее мама. Профессор его похвалил: «У вас прекрасный драматический баритон, даже не верится, что вы никогда не занимались вокалом». Стасу было всего 16 лет, в консерваторию поступать было рановато, а вот в училище уже можно. И Стас поступил в Ленинградское музыкальное училище имени Римского-Корсакова на вокальное отделение. Его взял в свой класс знаменитый педагог Иван Васильевич Мелентьев, который учился у концертмейстера самого Шаляпина.
Уже после первого курса училища вопреки всем правилам, его рекомендовали к поступлению в Ленинградскую государственную консерваторию имени Римского-Корсакова. Но из-за того, что Стасу было всего семнадцать, пришлось сначала поступать на подготовительный курс. В это же время стал серьезно заниматься дзюдо. Только через годы он понял, что на этих тренировках сломал носовую перегородку и она сместилась. Для голоса это имело трагические последствия. В результате ко второму курсу из разряда самых перспективных вокалистов он попал в ряды профнепригодных и безголосых. И из «консы» отчислили. Затем один год проучился в консерватории в Амстердаме.
Стас был уверен, что обязательно станет звездой. И действительно, вскоре уже играл главные роли в детском музыкальном театре «Зазеркалье», где обрел и любовь зрителей, и первую жену. Там же, кстати, встретил и Дениса Клявера. Во время встречи выяснилось, что отец Стаса — любимый музыкант Дениса (Михаил Костюшкин — известный питерский джазовый саксофонист), а Илья Олейников — любимый актер Стаса.
Вот так в 1994 году и родилась группа «Чай Вдвоем». Первым продюсером коллектива был Сергей Курехин. В течение двух лет группа сотрудничала с Лаймой Вайкуле, исполняя по несколько номеров в ее концертных программах. В 1999 году «Чай Вдвоем» дал первый большой сольный концерт в Санкт-Петербурге.
За время существования коллектива музыканты сочинили более ста песен.
В составе группы «Чай Вдвоем» записал альбомы: «Я не забуду…» (1996), «Попутчица» (1998), «Ради тебя» (1999), «Неродная» (2000), «Ласковая моя» (2002), «10 тысяч слов о любви» (2005), «Утреннее чаепитие» (2005), «Вечернее чаепитие» (2005), «Прости…» (2007), «Белое платье» (2012).
Хиты: «Просто друг», «Белое платье», «Желанная», «Сынок», «24 часа», «День рождения», «Ласковая моя».
Снимался в фильмах: «Моя прекрасная няня», «Али-Баба и сорок разбойников», «Тайский вояж Степаныча», «Испанский вояж Степаныча» и др.
В 2008 году совместно с Денисом Клявером создал продюсерскую компанию «Чай Вдвоем production», которая продвигает новые проекты, среди них – молодежный проект «Мэри Club».
В 2011 году было объявлено о роспуске группы «Чай вдвоем», однако совместные выступления Костюшкина и Клявера не прекратились.
Стас перенес операцию, связанную с устранением проблем носоглотки, затем заново учился петь: брал частные уроки у педагога Ирины Божедомовой в течение нескольких лет. Через три года ежедневных занятий голос все-таки восстановился. И Стас смог наконец осуществить заветную мечту — создал свой коллектив, с которым исполняет теперь серьезную, классическую эстрадную музыку. Назвал его «Stanley Schulman's Band» («Стэнли Шульман Бэнд»), по фамилии деда. Музыканты исполняют песни 30-40-х годов ХХ века в новых аранжировках.
В 2012 году представил свой новый проект – группу «A-DESSA».
Принимал участие в телепроектах «Цирк со звездами» и «Смех в большом городе».
Участвовал в украинском телешоу«Зірка + Зірка» (аналог российского проекта «Две звезды») и победил в дуэте с Евгением Никишиным.
Занимается культуризмом и боксом.
Владелец нескольких пончиковых в Москве и Петербурге.
Первая супруга – Марианна (прожили вместе 15 лет)
Вторая супруга – Ольга (окончила Институт физкультуры им. Лесгафта. Поженились 29 мая 2003 года за месяц до рождения сына, прожили вместе три года)
Третья супруга – Юлия Клокова, танцовщица коллектива «Чай вдвоем» (выпускница Академии физкультуры. Поженились 22 июля 2006 года)
Сын – Мартин (2003), от второго брака
Сын – Богдан (01.11.2006), от третьего брака
В составе группы «Чай вдвоем»:
▪ Лауреат конкурса молодых композиторов имени Виктора Резникова (1994)
▪ Лауреат конкурса молодых исполнителей «Ялта - Москва транзит» (1995)
▪ Лауреат конкурса российских исполнителей «Большое яблоко Нью-Йорка (1995)
▪ Премия «Золотой граммофон» (2001-2006, 2010)
▪ Премия «Стопудовый хит» (2004)