A Companhia de Navegação Aérea Aerolloyd Iguassú S/A foi fundada em Curitiba em março de 1933. A apresentação do primeiro avião da empresa, um Klemm KI 31A, ocorreu no Campo de Marte (SP), pelo piloto alemão Fritz Buehler, formado pela Lufthansa. O tempo de voo entre São Paulo (Marte) e Curitiba era de 2h30, por causa da rota contornando a estrada de ferro ou rodagem, ou pela costa, depois que regularam o serviço. O Senhor Ivo Leão era seu Presidente. A empresa inicou operações com uma frota de duas aeronaves Klemm KI 31 A (PP-IAA e PP-IAB) para três assentos.
Em 30 de junho o governo autorizou a operação na rota Curitiba – São Paulo, inaugurada em 20 de julho com quatro frequências semanais, de terças às sextas-feiras. Em 1934 passou a ligar Curitiba a Joinville e em 1935 estendeu a rota até Florianópolis. Outras três aeronave foram adicionadas a frota, de modelo Stinson Relliant, para cinco pessoas, prefixos PP-IAC, PP-IAD e PP-IAE.
Com grandes dívidas e precária atuação, pois não conseguia cumprir os horários preestabelecidos devido as severas condições climáticas na região montanhosa que operava, a Aerolloyd foi vendida para a VASP em 28 de outubro de 1939.
