A PLUNA (Primeiras Lineas Uruguayas de Navigazion Aerea) foi fundada pelos irmãos Márquez Vaeza e Alberto y Jorge no dia 20 de novembro de 1936. O primeiro voo ocorreu no mesmo mês, na rota Montevidéu - Salto - Paysandu, com dois De Havilland DH-90. Mas em 1943 as operações foram suspensas devido a Segunda Guerra Mundial. Com aeronaves de origem europeia, a Pluna não conseguia peças de reposição para a sua frota. A saída foi a aquisição de aeronaves americanas: dois DC-2 e três DC-3. Com a nova frota, a companhia pôde voltar a operar em 1945.
Em maio de 1948 foi inaugurada a primeira rota internacional: Montevidéu - Porto Alegre com o DC-3.
Em 1951 a companhia foi estatizada iniciou uma expansão internacional. Em 1952 foi inaugurada a rota para Assunção, em 1954 para São Paulo e em 1955 para Buenos Aires, Rosário e Córdoba.
Em 1958 a companhia começou a receber Vickers Viscount, que foram usados nas rotas para Buenos Aires, Assunção, Porto Alegre, São Paulo e Rio de Janeiro. No entanto a companhia enfrentou grandes dificuldades nos anos 60, devido a questões políticas no país, chegando inclusive a cancelar os voos para o Brasil. Essa época também foi marcada pelo fim dos voos domésticos operados pela empresa, que chegaram a ser nove ao todo. A partir dos anos 70 apenas Montevidéu e Punta del Este recebiam voos a Pluna.
A Pluna entrou na era do jato em dezembro de 1969 com o recebimento do primeiro Boeing 737-200, que foi empregado imediatamente no voo para Buenos Aires.
Em 1975 a frota foi ampliada com três Vickers Viscount (ex-Vasp), que passaram a operar para Porto Alegre.
Em 1981 a Pluna chegou em Madrid e Curaçao com um Boeing 707 ex-Aerolineas Argentinas. Na rota para Madrid, a companhia também usou um Boeing 767 da Spanair e um DC-10-30 da Varig.
Em 1986 a companhia inaugurou voos para Santiago, com o Boeing 737.
Em junho de 1995 a Varig comprou 49% da Pluna. Com isso a companhia lançou uma nova identidade visual, baseada na da Varig.
Em 2000 a companhia recebeu o seu próprio Boeing 767-200ER, que ficou no lugar do DC-10.
Em dezembro de 2001 a companhia recebeu o Boeing 737-300, que operou na rota para São Paulo e Buenos Aires.
Em 2002 recebeu um Boeing 767-300ER, que substituiu o 200.
Em 2003 a companhia recebeu um Boeing 757-200 (para voos charter) e um ATR-42-300.
Em 2005, devido crise financeira da Varig, esta saiu do controle da empresa e a Pluna voltou a ser controlada pelo governo uruguaio.
Em janeiro de 2007 o Leadgate Investments passou a controlar a companhia, anunciou a vinda de quinze Bombardier CRJ-900 e lançou uma nova identidade visual.
Em fevereiro de 2008 chegou o primeiro CRJ-900. Com a chegada de mais CRJ-900, a companhia foi substituindo todas as outras aeronaves da frota. A companhia deixou de voar para Madrid, em março de 2008, após a retirada do Boeing 767 da frota. Em contra partida a Pluna inaugurou novas rotas para o Brasil: Curitiba em 2008, Foz do Iguaçu em 2009, Campinas em 2010 e Belo Horizonte e Brasília em 2011.
Em abril de 2010 a Pluna anunciou uma parceria com a Jazz (subsidiária da Air Canada), onde a Jazz adquiriu 33% da controladora da Pluna, a American Regional Aviation Co.
Em 2012 a situação financeira da companhia vinha se agravando e a Pluna atrasou a entrega de novos jatos CRJ-900 e cancelou a rota Montevidéu - Campinas. Em julho os funcionários da companhia iniciaram uma greve, o que agravou ainda mais a situação da companhia. No dia 5 de julho a companhia suspendeu todas as operações.