La aerolínea se fundó en 1992 con los aviones de la recién separada división de Aeroflot-Vologrado. Inicialmente su nombre era Volga Airlines, que fue posteriormente cambiado a Volga-Aviaexpress. Luego el nombre se cambió nuevamente a Air Volga. El 1 de abril de 2010, Air Volga se declaró en quiebra después de una deuda que venia creciendo desde dos años antes, dicha deuda superaba los 500 millones de rublos. Tras la desaparición de la aerolínea la mayoría de sus rutas, equipos y su base principal pasaron a manos de la compañía chárter, también rusa, RusLine.^[1]​

Al momento del cierre definitivo de la aerolínea, esta operaba las siguientes aeronaves.^[2]​^[3]​

• 7 Canadair CRJ200

• 1 LET L-410 Turbolet

• 1 Tupolev Tu-134A3

• 2 Yakovlev Yak-40

• 6 Yakovlev Yak-42

Al momento del cierre de la aerolínea, esta operaba los siguientes destinos.^[4]​

• Ekaterimburgo - Aeropuerto Internacional de Ekaterimburgo-Koltsovo
• Krasnodar - Aeropuerto Internacional de Krasnodar-Pashkovsky base
• Moscú - Aeropuerto de Moscú-Domodédovo
• Nalchik - Aeropuerto de Nalchik
• Nizhnevartovsk - Aeropuerto de Nizhnevartovsk
• San Petersburgo - Aeropuerto de Pulkovo
• Samara - Aeropuerto Internacional de Samara-Kurumoch
• Surgut - Aeropuerto Internacional de Surgut
• Volgogrado - Aeropuerto Internacional de Volgogrado base

  Aeropuerto Internacional de Zvartnots

  Aeropuerto Internacional de Hurghada Aeropuerto Internacional de Sharm el-Sheij

  Aeropuerto Internacional de Dubái

  Aeropuerto Internacional de Arktau

  Aeropuerto de Antalya Aeropuerto Internacional Atatürk Aeropuerto de Dalaman

• El 24 de agosto de 2004, un Tu-134A3 explotó en pleno vuelo después de que terroristas chechenos plantaran una bomba en el avión. Los restos de la aeronave cayeran en Tula. 43 personas murieron en el accidente. Ese mismo día, los mismos terroristas plantaron una bomba en un Tu-154B2 de S7 Airlines, la cual explotó cuando el avión volaba sobre el óblast de Rostov, murieron las 46 personas a bordo.^[5]​^[6]​