The airline started operations on 19 June 1993, with Boeing 727-100 aircraft painted with the yellow, blue and red colors of the flag of Colombia, initially flying to Colombian coastal cities, such as Santa Marta, Cartagena, and San Andrés from Bogotá.

In the first months of operations, AeroRepública added new domestic destinations such as Cali, Medellín, Barranquilla, Montería, and Leticia.

During the first years of operations, AeroRepública's reputation became tarnished due to constant mechanical problems with its ageing fleet, low punctuality, and mismanagement.

The airline's board of directors reversed the situation by restructuring its business processes, launching a new corporate image, acquiring a fleet of McDonnell Douglas MD-80s, eliminating unprofitable routes, and adding the slogan "Live the Change" on advertisements.

[citation needed] In 2005, Panama's flag carrier, Copa Airlines, wanted to enter the Colombian market.

AeroRepública adopted a corporate image similar to Copa's and Continental's (now United) and began the retirement of the MD-80 fleet, in favor of the more efficient Embraer 190 and Boeing 737-700 aircraft.