It started out on 1965, with owner Osvaldo Gonzalez piloting a plane with 3 passengers from Vieques to Humacao. A Cherokee plane and another airplane were also acquired later, allowing the young airline to serve Isla Verde International Airport.
1968 saw Vieques Air Link become sort of an international airline, adding a flight to St. Croix in the Virgin Islands. (The Virgin Islands are only technically an international destination, because, like Puerto Rico, they are half independent from the United States.)
1980 saw the building of Fajardo airport and Vieques Air Link started flights to the new airport immediately. The 1980s were flourishing times for the small company and the frequency of flights to San Juan, Humacao and Culebra grew considerably. In 1989, Vieques Air Link lost its whole fleet to Hurricane Hugo. However, 7 Islander and 3 Trilander planes would rise again to the skies soon after and keep Vieques Air Link's name high up in the air.
The 1990s saw VAL get into financial trouble, but ironically, what was a problem for some, was a blessing for another. With the Vieques conflict, more and more Puerto Ricans began flying Vieques Air Link every day to go to military camps to protest, and the police also had to fly their personnel and the people arrested in those areas on VAL planes at various times. Others, like political leaders Ruben Berrios and Fernando Martin, and the 2002 Miss Puerto Rico, who hails from Vieques, have had pictures taken by the press aboard VAL planes while flying to Vieques, giving the airline a new wave of unpaid-for promotional attention.