Костадин Андреев е роден на 22 май 1968 година в Стара Загора. В семейството му няма музиканти, а самият той мечтае за театралната сцена. Записва се в Пловдивското училище за сценични кадри, за да се подготвя за изпитите в НАТФИЗ. Това са годините, в които се влюбва в музиката. Деветнайсет годишен започва да учи оперно пеене при Соня Хамерник и две години работи като помощник-режисьор в Старозагорската опера, докато тайно се подготвя за изпитите в Музикалната академия. Резултатът от труда и силното му желание не закъснява и той е приет, и то на първо място в списъка.

Завършва Академията през 1994 г. в класа на проф. Реса Колева, но дебютът му на професионална сцена е две години преди това. На сцената на Бургаската опера изпълнява ролята на Рудолфо в „Бохеми“. След тази изява той впечатлява с бързината и лекотата, с които изгражда персонажите си. За три години на бургаска сцена Костадин Андреев реализира главни роли в осем различни постановки: „Бохеми“, „Риголето“, „Дон Карлос“, „Фауст“, „Травиата“, „Кармен“, „Аида“ и „Отело“. През 1996 г. дебютира на Пучиниевия фестивал в Торе дел Лаго като Калаф в „Турандот“, където главната роля се изпълнява от самата Гена Димитрова. Година по-рано вече е солист в Националната опера. Само за първите три месеца от назначаването си в Софийската опера Андреев прави четири от най-тежките тенорови партии – играе в „Тоска“, „Турандот“, „Луиза Милер“ и „Бал с маски“. Тук идва и респектиращата констатация – през първите 10 години той прави рекордните 31 роли. Изпълнява едни от най-известните заглавия от Верди, Понкиели, Пучини, Гуно, Халеви, Бизе, Масне, Мусоргски, Стравински, Владигеров. И така до днес, когато след 26 години творчески път той е изиграл 43 роли!

Певецът е работил с големи имена от оперния свят като диригентите Антон Гуаданьо, Сейджи Осава, Марчело Виоти, Валерий Гергиев, Кацуши Оно, Руслан Райчев, Иван Вульпе, Борис Хинчев, Михаил Ангелов, Методи Матакиев, Георги Нотев. Негови партньори на сцената са били световноизвестните Агнес Балтса, Мишел Крайдър, Гена Димитрова, Райна Кабаиванска, Анна Томова-Синтова, Ренато Брузон, Лео Нучи, Феручо Фурлането, Никола Гюзелев.

Гастролира с голям успех на престижните сцени на Виенската Щатсопера, театрите в Торино, Карлсруе, Сент Гален, на Пучиниевия фестивал в Торе дел Лаго и фестивала на Валерий Гергиев в Ротердам. Неговият дон Хозе, който играе в Париж, френската преса нарича „вокален и артистичен пламък“.

Костадин Андреев участва и в „Пръстенът на нибелунга“, постановка на акад. Пламен Карталов и в „Янините девет братя“ от Любомир Пипков, с които спектакли Софийската опера и балет триумфира на сцената на Болшой театър в Москва.