О. М. Виноградов родился 1 августа 1937 года в Ленинграде, ныне - Санкт-Петербург.
В 1958 году окончил ЛАХУ имени А. Я. Вагановой.
В 1958—1965 годах — артист, ассистент балетмейстера, балетмейстер Новосибирского театра оперы и балета.
В 1967 году окончил балетмейстерский факультет ГИТИСа.
В 1967—1972 годах — балетмейстер в ЛАТОБ имени С. М. Кирова
В 1973—1977 годах — главный балетмейстер ЛМАТОБ.
С 1977 до 2001 (фактически до 1997 года) — художественный руководитель балета и главный балетмейстер ЛАТОБ имени С. М. Кирова (с 1992 года — Мариинский театр).
Ставил также балеты в Одессе, Минске, Риге, Таллине, Фрунзе, Дрездене, Будапеште, Софии, Берлине.
В 1990 году основал в Вашингтоне Universal Ballet Academy (Кировская балетная академия), в которой фундаментом стала петербургская школа. В том же году становится артистическим директором компании Юниверсал балет в Сеуле.
В 1994 г. организовал Санкт-Петербургский театр камерного балета.
В феврале 2008 года после 18 лет преподавания в академиях Вашингтона и Сеула Олег Виноградов возвращается в Санкт-Петербург в качестве главного приглашённого балетмейстера Михайловского театра.
Декан факультета режиссуры музыкального театра Санкт-Петербургской консерватории.
Одни из последних постановок О. М. Виноградова: «Золушка» С. Прокофьева в Музыкальном театре им. Станиславского и Немировича-Данченко (Москва, 2006), «Ромео и Джульетта» в Михайловском театре (Санкт-Петербург, 2007) и «Ромео и Джульетта» в Сеуле в 2006 году.
В Одесском академическом театре оперы и балета: