Assiut and Sharm el Sheikh in Egypt became served by the carrier for the first time in 2009, with flights to the latter initially operated on a seasonal basis.
In 2011, the airline started services to three cities in Turkey: Adana, Antakya and Istanbul.
Also that year, Lahore in Pakistan became the second city served in the country, after Karachi.
In February 2013, flights to Yanbu from Dammam were launched. Also that month, the airline started flying from Dammam to Khartoum, with the Sudanese capital becoming the first international destination ever to be linked to the Saudi city.
In February 2014, Flynas introduced its Global Flight Routes program, aimed at offering affordable rates to passengers for flights between Jeddah and points in Africa, Asia and Europe, and at carrying religious tourists to Saudi Arabia.
Flynas became the first low-cost carrier to serve the Saudi Arabia-UK market when it launched the Jeddah–London Gatwick service, its first European long-haul route, in April 2014.
Medium-haul routes to Karachi and Lahore were also planned, along with long-haul services to Jakarta, Kuala Lumpur, Casablanca, Manchester and Islamabad. Flights to Iran were also due to commence by the same time.
Manchester became the airline's second destination in the United Kingdom on 7 May 2014.
Cairo was made part of the route network in June 2014, making the Egyptian capital the carrier's seventh destination in the country.
The London-Gatwick–Riyadh sector would also be served from 27 July the same year.
A month later, it was informed that services to Manchester would be discontinued starting August 2014, just after three months of operations.
That month, the Indian market was expected to be served for the first time with flights to Hyderabad, followed by Calicut in September 2014.
Plans were also to serve France next as well as China, Philippines, Nigeria and South Africa later on.
Flynas also expected to serve the US market in 2015.
Manchester was removed from the carrier's list of destinations in early August 2014.
In October 2014, Al-Qassim was incorporated to the route network.
Also that month, the airline announced the cancellation of most of its long- and mid-haul services owing to poor performance.
At April 2015, Flynas' three top domestic routes in terms of available seats were Jeddah (JED)–Riyadh (RUH), Dammam (DMM)–RUH and JED–DMM.
The carrier also performs Hajj services.