Obwohl das Gründungsdatum von Cruzeiro do Sul, deren vollständiger Name Servicos Aereos Cruzeiro do Sul lautete mit dem 16.1.1943 angegeben wird, reichen die Wurzeln dieser Fluggesellschaft bis in das Jahr 1927 zurück, als mit Hilfe der alten Lufthansa die Syndicato Condor ins Leben gerufen wurde. Diese bediente mit Dornier Merkur und Dornier Wal die Strecke Natal - Rio.
1929 erfolgte eine Umbenennung in Aereos Condor und ab 1934 der erste grenzüberschreitende Verkehr zu einigen Städten in Chile und nach Buenos Aires. Im Jahr 1941 stand abermals eine Umbenennung an, dieses Mal in Servicos Aereos Condor. Ab 1942 löste man sich aus dem deutschen Einfluß, als Brasilien Deutschland den Krieg erklärte.
Ein Jahr später erfolgte die letzte Umbenennung in Servicios Aereos Cruzeiro do Sul. Die Flugzeuge der Typen JU-W.33, Ju-52, und FW-200 wurden durch DC-3 ersetzt und bis 1953 besaß Cruzeiro insgesamt 52 Maschinen diesen Typs.
1946 kamen C-54, 1954 CV-340 und 1958 CV-440 zur Flotte. Nicht unerwähnt sollte sein, dass die Gesellschaft von 1965 bis 1971 vier Consolidated Catalina einsetzte. Mit der Caravelle stieß am 10.12.1962 das erste strahlgetriebene Flugzeug zu Cruzeiro. Im Jahr 1965 konnte die Airline die Flugzeuge und auch große Teile des Streckennetzes von der in Konkurs geratenen Panair do Brasil übernehmen. Für die unwegsamen Regionen, aber auch für die Inlandstrecken setzte Cruzeiro ab 1967 die NAMC YS-11 ein.
Ab 1975 erwarb VARIG 65 % an Cruzeiro und erhielt so Zugang zu wichtigen Zielen im Innern des Landes. Im gleichen Jahr wurden die ersten L-188 von Varig an Cruzeiro gegeben und B-737 stießen zur Flotte. 
Cruzeiro führte am 20.6.1980 ihren ersten A-300-B4 ein. Obwohl die Gesellschaft unter ihren Namen fliegen konnte, änderte sich dieses mit der vollständigen Übernahme der Airline durch VARIG am 1.1.1993. Ab diesem Zeitpunkt wurde die gesamte Flotte und das ausgedehnte Streckennetz von Varig übernommen.