تأسست الشركة في الأول من يناير 1995 وبدأت أعمالها في يونيو 1997 بسلسلة من الرحلات الجوية لنقل الحجاج إلى جدة. وقد كانت الرحالات في البداية تنطلق من غزة، ولكن بسبب الحظر الإسرائيلي فقد أصبحت أعمال الشركة تجري في بور سعيد في شمال مصر.
جداول الرحلات بدأت في 23 يوليو 1997 برحلات من العريش إلى الأردنوالسعوديةوالإمارات. وقد قامت الشركة بنقل مركزها إلى غزة عقب افتتاح المطار هناك في نوفمبر 1998. توقفت أعمال الخطوط الفلسطينية في أكتوبر 2000 عقب اندلاع انتفاضة الأقصى وأجبرت على الانتقال إلى مطار العريش الدولي في ديسمبر 2001 بعد أن دمرت القوات الإسرائيلية مدرج المطار الوحيد في غزة.
الخطوط الفلسطينية مملوكة بالكامل للسلطة الوطنية الفلسطينية.
حتى أغسطس 2006 كان أسطول الخطوط الفلسطينية يتكون من ثلاث طائرات فقط هي طائرة بوينغ 727 تتسع لعدد 158 راكباً (12 راكب في الدرجة الأولى و146 في الدرجة الاقتصادية) وطائرتي فوكر 50 سعة 48 راكباً.[6]