Музыкальная деятельность Олега Погудина началась в 1979—1982 годах в детском хоре Ленинградского радио и телевидения под управлением Ю. М. Славнитского, в котором он сразу же стал одним из солистов. К этому времени относятся первые выступления юного певца на больших концертных площадках (БКЗ «Октябрьский», Большой зал Филармонии им. Д. Шостаковича, Государственная Академическая Капелла им. М. Глинки), а также первые записи на радио и телевидении. Архивные записи тех лет О. Погудина (согласно «Энциклопедии Кирилла и Мефодия») «…доныне транслируются по петербургскому радио, поражая слушателей чистотой голоса и уровнем исполнительского мастерства 'питерского Робертино Лоретти'».
По окончании школы Олег Погудин мечтал поступить в Ленинградскую консерваторию, но шестнадцатилетнему юноше посоветовали подождать пока окрепнет голос и прийти попозже. Не желая ждать, в 1985 году он стал студентом актёрского факультета (мастерская А. Н. Куницына) Ленинградского государственного института театра, музыки и кинематографии им. Н. К. Черкасова. Здесь Погудин продолжал серьёзно заниматься вокалом, и его дипломной работой стал моноспектакль, в котором автор исполнял песни из репертуара Александра Вертинского, причём «не копировал манеру пения знаменитого русского шансонье, а искал свои выразительные вокальные краски, интонации, акценты». Пройдя в 1989 году стажировку в Театральном центре им. Юджина О’Нила (Eugene O’Neil Theater Center), в США (по линии Американского Национального театрального института), Погудин принял участие в заключительном музыкальном представлении на сцене Линкольн-центра в Нью-Йорке. В 1990 году он закончил СПбГАТИ, получив диплом с отличием.
В 1990 году Погудин представил публике оригинальную программу «Я — артист!» по песням А. Н. Вертинского. Тогда же он стал актёром Санкт-Петербургского АБДТ им. Горького, на сцене которого работал вплоть до 1993 года. В 1991 вышел первый большой диск О. Погудина «Звезда Любви». Год спустя по приглашению Шведского культурного центра он провёл два концертных тура по Швеции, с большим успехом исполняя русские романсы и народные песни; считается, что именно Швеция дала «молодому исполнителю певческую путевку в жизнь». С 1993 года Погудин посвящает себя исключительно концертной деятельности — как в России, так и за рубежом, постоянно работая на региональных радио- и телестудиях.
В течение 1993—1996 годах на РТР вышли десять музыкальных фильмов с его участием, шесть из которых — «Жаворонок» (1993), «Звезда Любви» (1994), «Поговорим о странностях любви» (1994), «Цыганский романс» (1995), «Русская песня и старинный романс» (2-х частях, 1995-96) — были посвящены непосредственно его творчеству. В 1997 году Олег Погудин стал лауреатом фестиваля «Глас Ангельский России» и был удостоен награды «Ангел Трубящий», в 1999 году получил "Царскосельскую художественную премию, в 2002 году — премию «Триумф». В конце 2004 года ему было присвоено звание заслуженного артиста Российской Федерации.
В 2005—2006 годах Олег Погудин был ведущим программы «Романтика романса» на канале «Культура». С 2004 года он — преподаватель, а с 2007 года — доцент кафедры Эстрады и музыкального театра Санкт-Петербургской Академии театральных искусств. При участии Погудина на сцене Учебного театра были поставлены спектакли «Голоса ушедшего века», «Алые паруса», «Дорога без конца», ставшие заметными событиями петербургской театральной жизни.
В репертуар артиста входит свыше пятисот песен и романсов. Основные концертные программы: Русский старинный городской романс, классический русский романс, народная песня; военные песни; песни, романсы, вокальные произведения зарубежных авторов. Особое место в творчестве артиста занимают монографические программы, посвящённые памяти известных исполнителей отечественной эстрады: А. Н. Вертинского, Б. Ш. Окуджавы, П. К. Лещенко.
В 2000-х годах особое внимание артиста было сосредоточено на работе над серией концертов и записей под названием «Русскому Гению», цель которой — воплотить на сцене и в записи произведения камерного вокального жанра на стихи русских поэтов XIX — начала XX вв. В рамках этой программы проходит постоянное сотрудничество с литературными музеями России, как то: Государственный музей-заповедник А. С. Пушкина «Михайловское», музей-усадьба Л. Н. Толстого — Ясная Поляна, музей-усадьба А. С. Грибоедова — Хмелита и др.