The origins of SolTrans lead back to the early 20th century between two independent bus companies who served southern Solano County. These two companies were eventually acquired by the cities of either of Vallejo or Benicia, before consolidating to become Solano County Transit.
The Vallejo Bus Company was founded by Hartley Lowell in 1919. In 1935, the Vallejo Bus Company began to change hands between a number of owners until 1949 when the City of Vallejo took control of it.
However, the Vallejo City Council opted to close it in 1956 due to financial restraints. In response, community leaders led by Senator Luther Gibson created the Vallejo Citizens Transit Corporation (VCTC) in hopes of continuing services in Vallejo. The city subsequently transferred the fleet of thirteen buses to VCTC, who branded it Vallejo Transit Lines on May 1.
The Benicia-Vallejo Stage Line was founded 1915 by Milo Passalacqua. The Stage Line offered a route between Mare Island and Benicia, serving Vallejo's train stations and ferry docks. In 1982, the City of Benicia began operating Benicia Dial-a-Ride, a local demand responsive transit service. Service was later expanded on July 1, 1986 to include a fixed route between Benicia and the Pleasant Hill BART station; this service was called the Benicia Bay Connection. The city also began subsidizing the Benicia-Vallejo Stage Line. On October 1, 1986, the Bay Connection and Stage Line were merged to become Benicia Transit. This new company was managed by Community Transit Services, who were eventually acquired by Laidlaw. During the 1990s, Benicia Transit adds a number of additional routes, such as the Southampton Express (1991-2001) and as a few school tripper routes. It also purchase five used Gillig Phantoms for their main route and begin serving the Martinez Amtrak station between 1994 and 1997, before dedicating a route to it in 2005.
MV Transportation was awarded a contract to operate Benicia Transit in 2000, who would acquire controlling interest in VCTC five years later, transforming it into an MV subsidiary. In 2001, the Benicia Flyer route serving the Southampton hills operated for one year, before being discontinued due to low ridership and replaced with the Benicia Rocket, a route serving the Benicia Industrial Park. By October 2005, all named routes were converted into numbers: the main Vallejo/Pleasant Hill eventually being Route 75; the Amtrak being Route 23, and school trippers being Routes 15 through 18. 2006 saw Benicia Transit being re-branded as Benicia Breeze, replacing its dial-a-ride service into deviated fixed-routes and reducing its school tripper routes to two. Route 75 was eventually retired in favor of Vallejo Transit Route 78, which extends the route to Walnut Creek.