Po upadku ZSRR rozpoczęto rozmowy o ustanowieniu stałych połączeń lotniczych pomiędzy Izraelem a Rosją, porozumienie udało się jednak osiągnąć dopiero w 1991. Pierwsze loty czarterowe rozpoczęto w listopadzie 1991, jednak bardzo szybko okazało się, że ograniczona liczba samolotów El Al nie będzie w stanie przewieźć olbrzymiej liczby imigrantów pragnących osiedlić się w Izraelu. Z tego powodu zawarto stosowne umowy handlowe i porozumienia z Aerofłotem i w ciągu trzech lat przewieziono do Izraela ponad 400 tysięcy imigrantów.
W 1995 El Al poinformowały o planie uzyskania w roku budżetowym 1995 piętnastu milionów dolarów zysku netto przy przychodach rocznych 1,2 miliarda (wzrost o 17,5% w porównaniu z 1994). Dzięki tym danym w lutym 1995 zniesiono w przedsiębiorstwie zarząd komisaryczny, który prowadził spółkę przez ostatnie dwanaście lat. W tym samym roku zainaugurowano loty na Daleki Wschód i podpisano porozumienie o współpracy z American Airlines. W czerwcu 1996 odbył się pierwszy lot do Ammanu w Jordanii.