The origins of the Veterans of the Abraham Lincoln Brigade (VALB) can be traced to a meeting that Steve Nelson, David McKelvy White and William Lawrence organized for veterans of the Spanish Civil War in New York City in December 1937. The Veterans of the Abraham Lincoln Brigade was officially formed two years later in December of 1939 when a constitution for VALB was adopted at the third National Convention of veterans. The Friends of the Abraham Lincoln Brigade (FALB), which had been the principal U.S. advocate for the American volunteers and Spanish Republicans during the Spanish Civil War, was disbanded at this time.

The "objects" of the organization, as stated in VALB's 1939 constitution, were to "keep alive the principles for which the Lincoln Brigade fought in Spain"; to assist in the medical and occupational rehabilitation of its members; to aid and advocate for all International Brigade prisoners still in Spain; to advocate for amnesty for "Republicans in Spain" and aid refugees of the Spanish Civil War; "to cooperate with all organizations and groups interested in promoting peace, democracy and civil liberties"; and finally "to maintain fraternal relations with organizations of veterans of the Spanish Republican Army in other countries."

From the end of World War II through the early 1960s, the leadership of VALB was often prevented from focusing solely on the organization's stated goals by the need to defend the organization from government charges of subversion. Dr. Edward Barsky, leader of the American medical volunteers in Spain during the Civil War and national chairman of the Joint Anti-Fascist Refugee Committee, was subpoenaed in 1946 to appear before the House Committee on Un-American Activities (HUAC). When he and his board refused to surrender financial records or to turn over the names of contributors and recipients of aid, Barsky was charged with contempt of Congress, convicted, and imprisoned. Veteran Steve Nelson was arrested in 1950 and put on trial for sedition. Nelson, along with Irving Weissman, was also arrested under the anti-Communist Smith Act and charged with subversion. Several veterans arrested under the Smith-McCarran Immigration Act in the 1950s faced deportation. A number of veterans were subpoenaed by HUAC, and ordered to testify as to whether or not they were or had been Communists. In 1953 VALB came under the scrutiny of the Subversive Activities Control Board (SACB), and two years later it was ordered to register with the United States Justice Department as a Communist-front organization. VALB refused and took the case to the Supreme Court. The Court decided in VALB's favor in 1968, but the VALB was not removed from the Attorney General's list of subversive organizations until 1971.

Threats from the Subversive Activities Control Board waned by the mid-sixties and thus freed from the costs, in time and money, spent on hearings and trials VALB expanded its reach. Although advocacy for Spanish refugees and political prisoners, and support for democratic reforms in Spain continued to be a primary interest, members of VALB pushed the organization to face other issues as well. The Civil Rights movement, Vietnam War protests, opposition to the proliferation of nuclear weapons, and support for the Sandinista rebels of Nicaragua were among the many issues and causes which VALB embraced.

From the 1960s and onward, the preservation and commemoration of the history of the Spanish Civil War became increasingly important to VALB. Members of VALB took part in reunions of the International Brigades in the German Democratic Republic, in Italy, and finally, after the death of Francisco Franco in 1975, in Spain. Members of VALB wrote memoirs and histories, gave interviews and recorded their reminiscences, lectured, took part in college symposiums, supported exhibits, and participated in film and television documentaries. The organization kept in touch with its multi-generational constituency through frequent mailings and through its newsletter, published in the early years under the title, The Volunteer for Liberty, and from 1957 as The Volunteer. In 1979 two archives for the Abraham Lincoln Brigade were established, a major one held at Brandeis University and administered by archivist, Victor Berch, and a smaller one at the University of California at Berkeley. The Brandeis collections were transferred to the Tamiment Library at New York University in 2001 and have since grown substantially through new donations. For many years VALB maintained an office at 799 Broadway in New York City; its last Secretary was Lincoln Brigade veteran Moe Fishman.