Родился 12 августа 1972 г. в г. Мары Туркменской ССР (ныне – Туркменистан) в семье военного.
В 1993 г. окончил СПВЗРКУ по специальности "инженер по эксплуатации радиотехнических средств", в 2006 г. - Северо-Западную академию государственной службы при президенте РФ (ныне - Северо-Западный институт управления — филиал Российской академии народного хозяйства и государственной службы при президенте РФ) по специальности "экономист".
С 1993 по 1998 г. служил в Вооруженных силах РФ. Был заместителем начальника Спортивного клуба армии Ленинградского военного округа.
В 1998-2000 гг. работал на различных должностях в аналитическом центре комитета государственного лицензирования правительства Ленинградской области.
С 2000 по 2006 г. - генеральный директор муниципального предприятия "Экология" в г. Всеволожске Ленинградской области.
В октябре 2005 г. был избран депутатом Совета депутатов муниципального образования "Всеволожское городское поселение".
В 2006-2007 гг. работал директором муниципального учреждения "Всеволожская муниципальная управляющая компания".
С 2007 по 2011 г. - депутат Законодательного собрания Ленинградской области IV созыва. 11 марта 2007 г. избран по списку регионального отделения Коммунистической партии Российской Федерации (КПРФ). В Заксобрании был председателем постоянной комиссии по экологии и природопользованию, являлся членом постоянной комиссии по жилищно-коммунальному хозяйству и топливно-энергетическому комплексу.
С 2009 г. - секретарь Ленинградского областного комитета КПРФ.
В 2011-2014 гг. - депутат Государственной думы РФ VI созыва. 4 декабря 2011 г. избран по списку КПРФ, баллотировался под первым номером в региональной группе №46 (Ленинградская область). Член фракции КПРФ, входил в состав комитета Госдумы по жилищной политике и жилищно-коммунальному хозяйству. 26 февраля 2014 г. депутатские полномочия Вадима Потомского были прекращены досрочно в связи с переходом на госслужбу.
14 октября 2012 г. баллотировался на пост губернатора Брянской области. Набрал 30,83% голосов избирателей. Проиграл выборы действующему главе региона Николаю Денину (65,22%).
В 2014-2017 гг. - губернатор Орловской области. 26 февраля 2014 г. указом президента РФ Владимира Путина назначен временно исполняющим обязанности главы региона. Сменил на этом посту Александра Козлова.
14 сентября 2014 г. одержал победу на выборах губернатора Орловской области, получив 89,17% голосов избирателей (баллотировался от КПРФ). Второе место занял кандидат от ЛДПР Виталий Утешев (3,74% голосов). 23 сентября Потомский официально вступил в должность. Одновременно возглавил правительство Орловской области.
В рейтинге эффективности глав российских регионов, составленном Фондом развития гражданского общества и опубликованном в июне 2016 г., входил в третью группу руководителей субъектов РФ (т. н. средний рейтинг). Делил 70-71-е места с Никитой Белых, губернатором Кировской области в 2009-2016 гг., с которым набрал одинаковое количество баллов - 50.
5 октября 2017 г. президент России Владимир Путин освободил Вадима Потомского от должности губернатора Орловской области, врио руководителя региона стал Андрей Клычков, руководитель фракции КПРФ в Мосгордуме, секретарь Московского городского комитета КПРФ.
С октября 2017 г. по декабрь 2018 г. - заместитель полномочного представителя главы государства в Центральном федеральном округе . Курировал сферы промышленного производства, АЭС, а также решение проблем мусорных полигонов.
С декабря 2018 г. - заместитель полномочного представителя президента РФ в Северо-Западном федеральном округе Александра Гуцана. Курирует вопросы природоохранной деятельности, экологии и транспорта.
Общая сумма декларированного дохода за 2015 г. составила 5 млн 759 тыс. руб., супруги - 258 тыс. 421 руб.
Общая сумма декларированного дохода за 2016 г. - 3 млн 357 тыс. руб., супруги - 803 руб.
Капитан запаса. Ранее имел звание подполковника. По результатам проверки, проведенной военной прокуратурой в 2015 г., приказы о присвоении ему воинских званий майора и подполковника были признаны незаконными и отменены.
Награжден орденом Дружбы (2017).