ARCA fue fundada en 1956 por iniciativa del capitán Hernando Pote Gutiérrez, quien se retiró de Avianca por desacuerdos con el jefe de la empresa, Martín del Corral. El capitán Gutiérrez quería crear una empresa de pasajeros y competir con Avianca adquiriendo las primeras aeronaves, dos Douglas DC-3 para transportes de pasajeros pertenecientes a una empresa llamada Tacata. La primera y única ruta regular que Arca logró operar fue Bogotá–Cúcuta por un valor de 42 pesos por pasaje. Se realizó una gran campaña publicitaria, en la que se anunció la nueva tarifa.

Por presiones de Avianca, Lloyd y Taxader, la Unidad Administrativa Especial de Aeronáutica Civil (SAUCA) canceló las rutas de pasajeros de ARCA en la década de 1960; entonces, no le quedó más opción que operar solo carga desde el Aeropuerto La Vanguardia. Tiempo después la base de operaciones fue trasladada al aeropuerto El Dorado de Bogotá. Durante esa década, Arca operó con 5 Douglas DC-3. La operación de carga conectaba a Bogotá principalmente con gran parte de los Llanos Orientales , a los que se sumaban los Curtiss C-46 (HK-1322).

A principios de la década de 1970, algunos de los DC-3 fueron vendidos a Aerosucre, Laos y Alianza, todos ellos operadores de carga en el Aeropuerto La Vanguardia, mientras se tramitaba ante SAUCA el permiso para iniciar la operación de la ruta de carga a Miami. En 1973, SAUCA autorizó a ARCA la operación de carga al Aeropuerto Internacional de Miami desde Bogotá, esta se hizo en escala intermedia en Barranquilla en el recién adquirido Douglas DC-6B. Así, ARCA entró en una fuerte competencia con Avianca, Aerocosta y Aerocondor Colombia en la ruta de carga a Miami. ARCA hacía parte de las Big Four aerolíneas de Colombia en ese entonces y era muy considerada entre otras aerolíneas, en ese punto a mediados de los 70 era la cúspide de su éxito.

En 1975, ARCA entró en la era de los jets al arrendar un Boeing 707-120F, con una amplia puerta de carga para transportar flores y productos perecederos entre Bogotá y Miami, principalmente, ruta que la SAUCA tenía aprobada. El 707 anteriormente pertenecía a la carguera suiza Phoenix Air, que conservó algunos emblemas durante su corta operación en ARCA. En 1977 la compañía logró la capacidad financiera suficiente para adquirir su primer Douglas DC-8-43 (registro HK-1854), a través de Alitalia, para incrementar las operaciones de carga entre Bogotá y Miami. Este sería el primer DC-8 operado en Colombia; además, introdujo la nueva imagen de los siguientes aviones ARCA, conservando los colores de la aerolínea italiana. Lo particular de este avión era que no tenía puerta de carga, por lo que las operaciones de carga y descarga tomaban mucho tiempo.

En ese momento, ARCA se convirtió en la primera aerolínea de carga colombiana en volar el DC-8 a Miami. Además, compró un simulador, instalado en la antigua zona de carga de Miami. ARCA se caracterizó desde entonces, hasta que cesó sus operaciones, por tener dos DC-8 operando simultáneamente. Otras ciudades se incluyeron en las operaciones de carga desde Miami, como Cali, Cartagena, Medellín, Barranquilla, San Andrés y Bucaramanga, cuando hubo demanda. En enero de 1981, se adquirió a Braniff el primer DC-8-50F con puerta de carga ancha, el HK-2587-X.

Con la adquisición de nuevos DC-8, el tipo de carga que se traía desde Miami comenzó a variar, transportando automóviles, repuestos y, en algunos casos, caballos. Para principios de esa década, ARCA cerró un contrato temporal con Air France para traer carga desde Martinica. A mediados de 1981, adquirieron un Douglas DC-8 en arrendamiento, a través de FA Conner,^[2]​cuya matrícula era N53CA, que operó durante algunas semanas. Para principios de 1982, llegó el segundo Douglas DC-8-50F con amplia puerta de carga, HK-2667-X, anteriormente operado por Japan Airlines, por lo que era conocido entre la tripulación de ARCA como japonés.

En esa época, el itinerario de los vuelos de ARCA con flores y otros artículos perecederos estaba programado para salir de Bogotá en la madrugada para llegar a Miami temprano en la mañana. La aeronave fue descargada y estuvo lista antes del mediodía para regresar a Colombia. A mediados de 1982, el Douglas DC-8 HK-2587-X sufrió un accidente llegando a Cali procedente de Miami, saliéndose de la pista debido a una falla hidráulica y pérdida de dirección de la rueda de morro, factor agravado por la pista mojada. La rotura en el aeropuerto duró tres días, mientras la aeronave era retirada y la pista despejada. La aeronave volvió a operaciones después de la reparación.^[3]​

A principios de los años 80, la llegada desde Miami al Aeropuerto Olaya Herrera de Medellín era considerada en ocasiones como una hazaña de los pilotos, ya que la aeronave llegaba con carga completa en la mayoría de los vuelos y ocasionalmente iba sobrecargada. En ocasiones, tras el aterrizaje, los neumáticos de la aeronave se desinflaban en la plataforma a causa de una válvula de seguridad que se sobrecalentaba debido al intenso frenado que era necesario para detener la aeronave. Además, solo la pista 19 estaba disponible para el aterrizaje de esta aeronave, incluso con viento de cola. Esto ralentizaba todos los vuelos en el Aeropuerto Olaya Herrera y facilitaba mucho el trabajo de los mecánicos si no salía ningún vuelo.

Durante la década de 1980, ARCA inició acuerdos operativos con la aerolínea de carga ecuatoriana ANDES, por lo que se le arrendó un Douglas DC-8, HK-2667X, con el que compartía vuelos al Antiguo Aeropuerto Internacional Mariscal Sucre de Quito desde Miami y Colombia. A finales de esa década, se adquirió un Douglas DC-8 adicional.

A principios de la década de 1990, luego de haberse firmado el Acuerdo de Cielos Abiertos del Pacto Andino,^[4]​especialmente con Venezuela, ARCA tramitó ante la SAUCA la autorización para transportar pasajeros entre Cartagena y Miami con siete frecuencias semanales en aviones Douglas DC-8 para 180 pasajeros por 279 dólares, cerca de la mitad de lo que costaba un pasaje ordinario; también solicitó permiso para volar con pasajeros las rutas Bogotá-Cartagena, Cartagena-Medellín y Cartagena-Cali. La solicitud de ARCA fue apoyada por la Corporación Nacional de Turismo (CNT). En la audiencia pública, su representante, Luis Baldión, dijo que se presentó la solicitud de que la entidad apoyaba la iniciativa que propende por hacer del turismo una industria. Decenas de colombianos en Miami unieron su voz para llamar a romper el monopolio y bajar las tarifas aéreas entre Estados Unidos y Colombia. En el programa radial Colombia la Grande, transmitido por WRHC, se recibieron llamados de la ciudadanía para apoyar a ARCA, quien además envió sus firmas de apoyo al titular de la SAUCA en ese entonces, José Joaquín Palacio Campuzano.^[5]​Días después de estudiar la petición, la SAUCA negó a ARCA la aprobación de estas rutas. La decisión adoptada se basó en la recomendación del Consejo Superior Aeronáutico,^[6]​que consideró inconveniente para la empresa, operar carga, movilizar pasajeros, en particular en las rutas más importantes para el país.

Tras conocer la negativa de la SAUCA, el capitán Gutiérrez fundó la aerolínea en Venezuela y aprovechando el acuerdo bilateral en el marco del Pacto Andino,^[7]​ comenzó a operar con rutas de pasajeros entre distintas ciudades de Colombia y Miami vía Maracaibo con equipos DC-8 a precios realmente más económicos. En 1992, se adquirió en leasing uno de los últimos Douglas DC-8-50F operados por la aerolínea, el N5842A. En junio de 1993, un niño polizón, Guillermo Rosales, de 13 años, fue encontrado con vida en el tren de aterrizaje de un DC-8 en el aeropuerto de Miami, a las 2 am, en un vuelo procedente de Bogotá. El hecho asombró a médicos y expertos en aviación ya que el niño sobrevivió a las condiciones extremas de temperatura y falta de oxígeno.

Los años 90 marcarían una crisis no solo para ARCA sino para todas las aerolíneas de carga colombianas, a causa de varias circunstancias combinadas en contra de la industria aérea en el país. La principal fue el narcotráfico, lastre que se requería combatir con una gran inversión en seguridad, regulada por la FAA (Administración Federal de Aviación) para operar en Estados Unidos, además de la restricción de ruido, que obligó a adoptar kits Stage I y hush, lo que aumentaría los gastos imprevistos que debían hacer las aerolíneas en sus DC-8, además de la descertificación que sufrió el país por el escándalo del gobierno de Ernesto Samper. Para mediados de 1994, uno de los Douglas DC-8, el HK-3125-X, terminó su vida útil y quedó en tierra. Se hicieron contactos para arrendar un McDonnell Douglas DC-10-10F, pero la transacción se canceló. Durante los años siguientes, cada vez era más difícil continuar con las operaciones de carga; la presión de la FAA se hacía cada vez más rigurosa mientras que la dura competencia de las aerolíneas de carga internacionales hacía menos rentable la operación.

El 24 de enero de 1997, ARCA fue intervenida por la SAUCA. El director de la entidad, Abel Enrique Jiménez, y el jefe de la Oficina de Control y Seguridad, capitán Germán Duarte, manifestaron que en el proceso de inspección, tuvieron que paralizar la operación que venían realizando las aeronaves de la empresa porque no cumplían con los requisitos para volar a Estados Unidos. Por lo que la empresa quedó bajo fuego por no haber completado la inspección de las aeronaves y el estado financiero de la empresa. La inmovilización de cada DC-8 representó para la empresa una disminución del 50% en sus ingresos y para inicios de 1996, la SAUCA fue rebajada por la FAA a la categoría dos, por no ejercer una inspección adecuada a las aerolíneas.

A mediados de 1997, la FAA multó a ARCA con una suma de 68.000 dólares, por no cumplir con un plan de mantenimiento. Según la FAA, ARCA realizó una serie de vuelos en el Douglas DC-8-55F entre junio de 1992 y agosto de 1993 sin el sistema de ventilación necesario para la puerta principal de carga dentro de un período estipulado. Estas decisiones, la falta de apoyo gubernamental y la descertificación fueron eventos que lamentablemente marcaron el cierre de la compañía. Sus tres DC-8, HK-2587X, HK-3746X y N5824A fueron inmovilizados en Miami y luego desguazados a finales de la década en el sector del aeropuerto conocido como el "Corrosion Corner".^[8]​^[9]​

ARCA prestó servicio a los siguientes destinos:^[10]​

• Barranquilla (Aeropuerto Internacional Ernesto Cortissoz)
• Bogotá (Aeropuerto Internacional El Dorado)
• Bucaramanga (Aeropuerto Internacional Palonegro)
• Cali (Aeropuerto Internacional Alfonso Bonilla Aragón)
• Medellín (Aeropuerto Internacional José María Córdova)
• San Andrés (Aeropuerto Internacional Gustavo Rojas Pinilla)
• Villavicencio (Aeropuerto La Vanguardia)

• Quito - Antiguo Aeropuerto Internacional Mariscal Sucre

• Fort-de-France - Aeropuerto Internacional de Martinica Aimé Césaire

• Miami - Aeropuerto Internacional de Miami

ARCA Colombia utilizó a lo largo de los años las siguientes aeronaves:^[1]​

• 1 x Boeing 707-120F
• 1 x Curtiss C-46 Commando
• 5 x Douglas DC-3
• 1 x Douglas DC-6B
• 2 x Douglas DC-8-43
• 1 x Douglas DC-8-51F
• 2 x Douglas DC-8-53F
• 3 x Douglas DC-8-54CF
• 1 x Douglas DC-8-55CF

• El 11 de agosto de 1982, un Douglas DC-3 (HK-337) de ARCA Colombia chocó contra un Curtiss C-46 (HK-124) de la aerolínea LACOL Colombia que se encontraba detenido. El piloto y el copiloto resultaron heridos. Los dos tripulantes del C-46 resultaron ilesos.^[11]​