The airline was established in 1982 to fly scheduled services between Egypt and Israel (on routes previously flown by Nefertiti Aviation), which for political reasons could not be handled by parent company EgyptAir. Services started using a Boeing 737-200 leased from EgyptAir and new routes from Egypt's tourist destinations followed. By the mid-1980s a Fokker F27 Friendship was also in use on these services. During 1982, a Boeing 707-320C, reg N18712 (c/n 19226, ex TWA) was leased and operated on behalf of EgyptAir on their flights to Europe, especially twice weekly MS782/781 Cairo-Copenhagen v.v.
Air Sinai ceased airline operations in its own right in 2002 and operates as a 'paper airline' for its parent company, EgyptAir using their aircraft without any markings identifying either carrier, although some have been spotted in Tel Aviv in full EgyptAir branding, Flights are not listed in EgyptAir schedules and do not appear in their website or route maps either.  As of 2014 Air Sinai flights are displayed on arrival and departure boards at Cairo Airport using the IATA code 4D. 
Air Sinai previously operated in its own livery as seen here.