Олег Шейнцис родился в городе Одессе в 1949 году. Учился в Одесской художественной школе и театрально-художественном училище. Некоторое время работал архитектором.
В 1977 году окончил постановочный факультет Школы-студии имени Вл. И. Немировича-Данченко при МХАТе им. А.П. Чехова (курс В.В. Шверубовича). В этом же году начал сотрудничать с Ленкомом, а с 1980 года - главный художник театра.
В содружестве с Марком Захаровым Олег Шейнцис создал художественный образ таких спектаклей театра, как "Жестокие игры", "Юнона и Авось", "Три девушки в голубом", "Оптимистическая трагедия", "Диктатура совести", "Мудрец", "Поминальная молитва", "Чайка", "Безумный день, или Женитьба Фигаро", "Варвар и еретик".
Автор декораций к спектаклям "Город миллионеров", "Шут Балакирев", "Плач палача", "Ва-банк". Оформлял спектакли в Лондоне и Тель-Авиве, Флоренции, Софии, Братиславе, сотрудничал с рядом московских театров, киностудиями.
Участник художественных выставок в России и за рубежом. С 1979 года занимался преподавательской деятельностью, профессор Школы-студии (ВУЗ) им. Вл. И. Немировича-Данченко при МХАТе им. А.П. Чехова.