Родилась 13 марта 1969 г. в Нарьян-Маре Ненецкого национального округа (с 1977 г. - Ненецкий автономный округ, НАО).
В 1992 г. окончила Рижский институт инженеров гражданской авиации им. Ленинского комсомола (с 1992 г. - Рижский авиационный университет; в 1999 г. ликвидирован) по специальности "инженер-экономист", в 2003 г. - Северо-Западную академию государственной службы по специальности "юрист", в 2013 г. - Российскую академию народного хозяйства и государственной службы при президенте РФ по специальности "психолог, преподаватель психологии".
Кандидат экономических наук. В 2006 г. в российском государственном социальном университете защитила диссертацию на тему "Развитие региональной социально-экономической системы: на материалах Ненецкого автономного округа".
С 1993 г. работала в администрации г. Нарьян-Мара. В 1993–1996 гг. была экономистом, бухгалтером, в 1996-2001 гг. — заведующей финансовым отделом администрации города.
С 2001 по 2006 г. - заместитель главы администрации Нарьян-Мара.
В 2006-2008 гг. возглавляла управление финансов администрации Нарьян-Мара.
2 декабря 2007 г. участвовала в выборах в Государственную думу РФ V созыва в составе списка кандидатов от партии "Справедливая Россия: Родина/Пенсионеры/Жизнь" (третий номер в региональной группе №86, Ненецкий АО). По итогам распределения мандатов в Думу не прошла.
18 мая 2008 г. баллотировалась на пост главы Нарьян-Мара на досрочных выборах. Заняла второе место из пяти с результатом 27,78%. Победу одержал Юрий Родионовский, набравший 36,49% голосов. Все кандидаты участвовали в выборах в порядке самовыдвижения.
С 2008 по 2009 г. Ольга Старостина вновь занимала должность заместителя главы Нарьян-Мара. Курировала экономику и финансы.
В 2009-2017 гг. - депутат, председатель Совета городского округа "Город Нарьян-Мар" II и III созывов. Участвовала в выборах от партии "Единая Россия". 11 октября 2009 г. была избрана во II созыв горсовета по списку партии (второй номер общей части регионального списка). 14 сентября 2014 г. избрана в III созыв по Центральному двухмандатному избирательному округу №5, набрав 31,36% голосов (получила мандат от округа вместе с Еленой Сопочкиной от "Единой России", 32,01%).
Была председателем Регионального координационного совета по взаимодействию с некоммерческими организациями НАО.
С апреля 2017 г. по сентября 2018 г. - заместитель губернатора Ненецкого автономного округа по делам ненецкого и других коренных малочисленных народов Севера. Курировала также вопросы межнациональных и межконфессиональных отношений. Была назначена на должность главой округа Игорем Кошиным, сохранила пост после того, как в сентябре 2017 г. регион возглавил Александр Цыбульский.
9 сентября 2018 г. избрана депутатом Андегского сельсовета VI созыва на дополнительных выборах по одномандатному округу №1. Получила 30 голосов из 39 (76,92%).
С 1 октября 2018 г. по 23 сентября 2020 г. - член Совета Федерации РФ - представитель от исполнительного органа государственной власти Ненецкого автономного округа. Входила в состав Совета по Арктике при Совете Федерации. Сложила полномочия по личному заявлению в сентябре 2020 г. Пост сенатора от НАО занял Дмитрий Гусев.
Член политического совета Ненецкого регионального отделения партии "Единая Россия".
Руководитель Ненецкого регионального отделения Союза женщин России, председатель регионального отделения Всероссийского совета местного самоуправления.