Verda grew up on a farm near St. Anthony, Idaho. After graduating from high school, she attended Albion Normal School and then Brigham Young University. Verda married briefly in the 1930s and had a daughter, and spent much of her time as a single mother in Boise. After the repeal of prohibition, Verda became the first director of the newly formed Idaho Liquor Commission.

After receiving a letter from James Farley, the Postmaster General and chairman of the Democratic National Committee, asking for volunteers to become a part of Roosevelt's New Deal, Verda and her daughter moved to Washington, D.C. She quickly became involved with organized labor, in the Department of the Interior, and the Securities and Exchange Commission. She also became active in the Young Democrats and became national vice-chairman for the organization during the Roosevelt era. During this time she became friends with Franklin and Eleanor Roosevelt.

In 1945, she began working for newly elected Idaho Senator Glen Taylor. Later, she joined the staff of Frank Church, who was elected in 1956. She first served as his governmental liaison and then as his chief of staff. In that position she became Church's chief political strategist and the de facto chief political strategist for the entire Idaho Democratic party. Without Barnes' tireless political efforts, it is quite likely that Frank Church would have been a one-term Senator.