The airline was founded in La Paz, Mexico in 1960 as an air taxi operator using a fleet of Cessna and Beechcraft airplanes, initially known as Servicios Aéreos . By the early 1980s the demand for domestic charter flights had grown enough that the larger Douglas DC-3 was added to the fleet. Scheduled services were launched in June 1982, initially interlinking La Paz, Tijuana and Hermosillo using Convair 340 aircraft. In 1989, international scheduled flights commenced, with Los Angeles being the first destination. By 1995 the fleet had been upgraded to only include jet aircraft of various Douglas DC-9 subtypes.
On 3 April 2006 all operations of Aero California were suspended by the Mexican Secretariat of Communications and Transport, after it was found that the airline was not complying with safety standards. It was given 90 days to correct the problems and was able to resume services on 11 August 2006. On 23 July 2008 (at a time when the route network consisted of 17 domestic destinations), the airline was again suspended, this time due to an alleged debt with the Mexican Air Traffic Control (SENEAM). This prompted a labor strike of the employees on 5 August, which technically continues to the present day. Aero California's license still remains valid to this day. In 2015, several of the companies' ex-employees protested once again, to demand unpaid wages.