En 1949 fúndase a cidade de Eilat, a cidade máis austral de Israel, seguidamente establécese Eilata Airlines para manter unha comunicación aérea directa coa zona central de Israel. A aeroliña foi propiedade de El Al e Histadrut (federación laboral de Israel), iniciando as súas operacións en 1950. Posteriormente pasou a denominarse Aviron, e finalmente Arkia Israel Airlines. No seu primeiro ano de servizo, transportou 13.485 pasaxeiros nos seus dous voos semanais, operados cunha aeronaveCurtis Commando.
Durante a década de 1950 a aeroliña continuou o seu crecemento, renovando a súa frota a aeronaves de maior tamaño (DC-3), e pasando a operar dous voos diarios. Isto permitiulles alcanzar un tráfico superior a 70.000 pasaxeiros anuais. Na medida en que a cidade de Eilat continuou crecendo durante a década de 1960, tamén o fixo Arkia, introducindo a aeronave jet Herald na súa frota, e expandindo a súa presenza con novas rutas a Xerusalén, Sharm el-Sheij, e Santa Caterina. Unha subsidiaria, Kanaf Arkia Airline and Aviation Services foi fundada cando Arkia Israel Airlines adquiriu o 50% das accións de Kanaf Airlines and Aviation Services, e para fins da década de 1960 comezou a operar voos regulares a través de Israel, desde Rosh Pina no norte até Ofira, no sur da península do Sinaí.
En marzo de 1980, Kanaf Arkia Airline and Aviation Services adquiriu a totalidade das accións de Arkia Israel Airlines, fusionando ambas as compañías. A aeroliña continuou crecendo rapidamente durante a década de 1980, incursionando no mercado de voos chárter internacionais e no mantemento de aeronaves. A aeroliña é propiedade de Kanaf-Arkia Airlines (75%) e os seus empregados (25%).
En febreiro de 2007, o Ministerio de Turismo de Israel outorgou a Arkia Israel Airlines licenzas para voar a Lárnaca (ruta que recentemente El Al deixara de operar), en Chipre; e a Dublín, Irlanda.
O 28 de novembro de 2002, aproximadamente 20 minutos antes de que estalase a bomba no Paradise Hotel de Mombasa (Kenya), un Boeing 757 de Arkia foi atacado con dous mísiles antiaéreos que non chegaron a impactar por pouco, logo de engalar do Aeroporto Internacional de Moi en Kenya. A aeronave puido aterrar sen problemas en Tel Aviv.
