Образовавшийся в 1990 году театр «Провинциальные танцы» постепенно набирал репертуар, создавались номера и миниатюры, которые в итоге составили две программы: «От Баха до…» (1990) и «Искусство импровизации» (1991).
Художником по костюмам и сценографом обеих программ была Ольга Паутова. Дальше была работа над костюмами к спектаклю Татьяны Багановой «Когда наступит время и придет Тот. Кто… (1993), к программе «Одиночество, пожалуй, любит меня больше, чем я его…» (1994). Именно в этих костюмах танцовщики театра получили премии на V Международном конкурсе танца в Париже, VIII Международном фестивале молодых балетмейстеров в Ганновере, Международном фестивале современной хореографии в Витебске, выступили на первых гастролях в США (American Dance Festival), Москве и Калининграде.
Сотрудничество Татьяны и Ольги продолжилось во второй половине девяностых: 1997 – сценография и костюмы спектакля «Мужчина в ожидании», 1999 – сценография (в соавторстве с Багановой) и костюмы (в соавторстве с Викторией Мозговой) спектакля «Кленовый сад». Обе постановки стали номинантами Национальной театральной Премии «Золотая Маска», а «Кленовый сад» стал обладателем двух «Масок» – за лучшую хореографию и лучшую работу художника в музыкальном спектакле.
В первой половине двухтысячных выпущены еще два спектакля, номинированные на «Золотую Маску», где Ольга стала соавтором сценографии и автором костюмов: «Тихая жизнь с селедками» (2001) и «Полеты во время чаепития» (2002). Эти спектакли, как и «Кленовый сад», долгое время живут в репертуаре театра: «Полеты…» в марте 2014 года показаны 59-й раз, а «Кленовый сад» в декабре 2019 года – 66-й.
В 2016 году Ольга Паутова стала директором Екатеринбургского театра современной хореографии «Провинциальные танцы», во многом – по инициативе Татьяны Багановой. Административная работа оставляет очень мало времени, но «художников бывших не бывает», и, поддавшись на уговоры Татьяны, Ольга взялась за сценографию и костюмы новой версии спектакля «После вовлеченности. Диптих. Часть II» (2017) и премьерного спектакля «Девушка с фарфоровыми глазами» (2018).