Вероника Долина родилась 2 января 1956 года в Москве, в семье авиаконструктора Аркадия Яковлевича Фишера и врача Людмилы Александровны Долиной. Дед по материнской линии, выходец из бессарабского местечка Вад-Рашков, участвовал в Гражданской войне в составе кавалерийской бригады Г. И. Котовского, затем был комиссаром Одесского артиллерийского училища. Брат — Александр Аркадьевич Долин — переводчик художественной литературы с японского языка. Училась в одном классе с Егором Гайдаром. Окончила музыкальную школу.
В 1979 году окончила Московский государственный педагогический институт им. В. И. Ленина, получив профессию учителя французского языка. Некоторое время работала в библиотеке, затем — в редакции специализированного журнала.
С 1971 года Долина начала писать песни и исполнять их, аккомпанируя себе на шестиструнной гитаре. К большинству своих песен Долина сама написала стихи и музыку, есть также песни на стихи Ю. Мориц и песни, написанные в соавторстве с А. Сухановым. С середины 1970-х Долина активно участвовала в жизни сообщества московского КСП, хотя значительная часть сообщества (особенно поначалу) критически относилась к «острой» творческой манере и подчёркнуто женской тематике её песен.
Как и у многих других бардов, регулярные публикации произведений у Вероники Долиной начались в эпоху перестройки. В 1986 году у неё выходит первый диск, вскоре — второй (тираж более 1 млн). В 1987 году она становится членом Комитета московских драматургов. В том же году у неё в Париже выходит первый сборник стихов.
В 1989 году фирма «Мелодия» издала компакт-диск Вероники Долиной «Элитарные штучки». На сегодняшний день у Долиной выпущено более 10 сборников стихов, 9 виниловых дисков, более 20 компакт-дисков.
В 2005 году была присуждена литературная премия «Венец».