Родился 19 февраля 1956 г. в Челябинске в семье Григория Степановича и Лидии Яковлевны Митяевых. Его отец был рабочим Челябинского трубопрокатного завода, мать вела домашнее хозяйство.
В 1975 г. Олег Митяев окончил Челябинский монтажный техникум (ныне в составе Южно-Уральского государственного технического колледжа) по специальности "техник-электрик". В 1975-1977 гг. проходил срочную воинскую службу в Москве. В 1981 г. окончил Челябинский государственный институт физической культуры (ныне Уральский государственный университет физической культуры) по специальности "тренер по плаванию", в 1991 г. - заочное отделение Государственного института театрального искусства им. А. В. Луначарского (ныне Российский институт театрального искусства - ГИТИС).
В разное время Олег Митяев работал монтажником, художником, дворником, выступал в ансамбле челябинского Торгового центра. В 1981-1985 гг. - преподаватель Челябинского института физкультуры, заведующий клубом в местном пансионате "Сосновая горка". С 1985 г. работал в Челябинской филармонии как вокалист и инструменталист. В начале 1990-х гг. переехал в Москву.
Олег Митяев начал писать песни с конца 1970-х гг. Успех пришел к музыканту после собственного исполнения в 1979 г. на Ильменском фестивале (фестиваль авторской песни, проходящий ежегодно с 1973 г. в Челябинской области) первой песни - "Как здорово". Эта композиция остается самым популярным произведением Митяева, считается неформальным гимном бардовского движения.
До 1986 г. выступал на фестивалях в дуэте с музыкантом Петром Старцевым. В 1987-1998 гг. работал вместе с гитаристом и аранжировщиком Константином Тарасовым. С 1998 г. выступает вместе с мультиинструменталистом и композитором Леонидом Марголиным, с 2006 г. третьим участником коллектива является гитарист Родион Марченко.
Среди наиболее известных песен Олега Митяева: "В осеннем парке", "Давай с тобой поговорим", "Соседка", "Француженка", "Лето - это маленькая жизнь", "Крепитесь, люди! Скоро лето!", "Родильный дом". Музыкант записал более 20 альбомов с собственными произведениями и песнями других авторов. В 2002 г. вышел альбом "Ни страны, ни погоста...", на котором Митяев исполнил песни, написанные Леонидом Марголиным на стихи поэта Иосифа Бродского. Неоднократно издавались сборники стихотворений Олега Митяева.
Он снимался в фильмах "Сафари №6" (1990, режиссер Андрейс Аболс) и "Убийца" (1990, Сергей Мартьянов). В 1992 г. исполнил роль поэта Владимира Маяковского в антрепризном спектакле "Большой Владимир".
С 2000 г. работает Благотворительный фонд культурных инициатив Олега Митяева (музыкант стал членом его попечительского совета). Организация проводит Ильменский фестиваль, реализует ряд благотворительных проектов и др.
Олег Митяев является соучредителем и первым заместителем председателя региональной общественной организации "Союз деятелей авторской песни".
Соучредитель ООО "Эксито" (работает в сфере аренды и управления недвижимостью), общественной организации "Самарский областной Грушинский клуб", межрегионального общественного фонда имени Михаила Евдокимова.
Народный артист РФ (2009).
Лауреат Царскосельской художественной премии (2003, 2009).
Женат третьим браком. Супруга - народная артистка РФ, актриса Государственного академического театра им. Евг. Вахтангова Марина Есипенко (род. 1965). Дети (от разных браков): Сергей, Филипп, Савва, Дарья.