Madinah offers nonstop service to 68 destinations, served by 33 airlines.
| Destination | Code | Country | Distance | Duration | Airlines |
|---|---|---|---|---|---|
| Jeddah | JED | Saudi Arabia | 323 km | 1h 10m | AT, SV, XY, RJ |
| Gassim | ELQ | Saudi Arabia | 453 km | 1h 10m | F3 |
| Tabuk | TUU | Saudi Arabia | 524 km | 1h 20m | XY, F3 |
| Riyadh | RUH | Saudi Arabia | 709 km | 1h 35m | SV, XY, F3 |
| Luxor | LXR | Egypt | 716 km | 1h 45m | SM |
| Arar | RAE | Saudi Arabia | 718 km | 2h 0m | F3 |
| Abha | AHB | Saudi Arabia | 762 km | 1h 40m | XY, F3 |
| Sohag | HMB | Egypt | 824 km | 1h 45m | SM |
| Amman | AMM | Jordan | 874 km | 1h 50m | RJ, XY |
| Jazan | GIZ | Saudi Arabia | 898 km | 1h 55m | F3 |
| Asyut | ATZ | Egypt | 914 km | 1h 48m | SM |
| Kuwait | KWI | Kuwait | 972 km | 1h 50m | KU, SV, J9 |
| Hofuf | HOF | Saudi Arabia | 992 km | 1h 50m | F3 |
| Cairo | CAI | Egypt | 1,026 km | 2h 0m | MS, SV, XY, F3, SM |
| Dammam | DMM | Saudi Arabia | 1,037 km | 1h 45m | XY, F3 |
| Giza | SPX | Egypt | 1,066 km | 1h 50m | XY |
| Bahrain | BAH | Bahrain | 1,115 km | 2h 0m | GF |
| Ahwaz | AWZ | Iran | 1,165 km | 2h 5m | J9 |
| Doha | DOH | Qatar | 1,205 km | 2h 15m | QR |
| Alexandria | HBE | Egypt | 1,213 km | 2h 0m | MS, SM |
| Abu Dhabi | AUH | United Arab Emirates | 1,514 km | 2h 30m | EY |
| Dubai | DXB | United Arab Emirates | 1,583 km | 2h 40m | EK, FZ, XY |
| Sharjah | SHJ | United Arab Emirates | 1,599 km | 2h 30m | G9 |
| Addis Ababa | ADD | Ethiopia | 1,724 km | 3h 0m | ET |
| Trabzon | TZX | Turkiye | 1,824 km | 3h 20m | XY, PC |
| Ankara | ESB | Turkiye | 1,837 km | 3h 30m | PC, VF |
| Muscat | MCT | Oman | 1,891 km | 2h 55m | WY, OV |
| Baku | GYD | Azerbaijan | 2,012 km | 4h 0m | XY |
| Istanbul | SAW | Turkiye | 2,055 km | 3h 35m | XY, PC, VF, F3 |
| Istanbul | IST | Turkiye | 2,114 km | 3h 35m | SV, TK |
| Aktau | SCO | Kazakhstan | 2,380 km | 4h 25m | KC |
| Quetta | UET | Pakistan | 2,760 km | 4h 15m | PK |
| Karachi | KHI | Pakistan | 2,774 km | 4h 5m | PK, XY |
| Sarajevo | SJJ | Bosnia and Herzegovina | 2,889 km | 4h 20m | XY |
| Monastir | MIR | Tunisia | 3,038 km | 5h 15m | SV |
| Enfidha | NBE | Tunisia | 3,075 km | 4h 50m | SV |
| Tunis | TUN | Tunisia | 3,119 km | 4h 20m | SV, L6 |
| Multan | MUX | Pakistan | 3,188 km | 4h 20m | PA, PK |
| Annaba | AAE | Algeria | 3,324 km | 5h 10m | AH |
| El Oued | ELU | Algeria | 3,340 km | 5h 5m | AH |
| Faisalabad | LYP | Pakistan | 3,348 km | 4h 50m | PK |
| Islamabad | ISB | Pakistan | 3,360 km | 4h 50m | PK |
| Shymkent | CIT | Kazakhstan | 3,373 km | 5h 0m | DV, KC |
| Constantine | CZL | Algeria | 3,413 km | 5h 25m | AH, SV |
| Batna | BLJ | Algeria | 3,427 km | 4h 45m | AH |
| Mumbai | BOM | India | 3,473 km | 4h 40m | SV, 6E |
| Lahore | LHE | Pakistan | 3,483 km | 4h 50m | PK |
| Sialkot | SKT | Pakistan | 3,489 km | 5h 0m | PK |
| Tamanrasset | TMR | Algeria | 3,489 km | 6h 0m | AH |
| Ghardaia | GHA | Algeria | 3,603 km | 6h 0m | AH |
| Algiers | ALG | Algeria | 3,721 km | 6h 0m | AH, SV |
| Marseille | MRS | France | 3,771 km | 5h 55m | TO |
| Lyon | LYS | France | 3,884 km | 6h 10m | TO |
| Almaty | ALA | Kazakhstan | 3,984 km | 5h 45m | DV, KC |
| Adrar | AZR | Algeria | 3,995 km | 6h 10m | AH |
| Astana | NQZ | Kazakhstan | 3,999 km | 5h 50m | KC |
| Oran | ORN | Algeria | 4,043 km | 6h 25m | AH, SV |
| Hyderabad | HYD | India | 4,096 km | 5h 23m | 6E |
| Paris | ORY | France | 4,214 km | 6h 35m | TO |
| London | LGW | United Kingdom | 4,496 km | 6h 45m | W9 |
| Casablanca | CMN | Morocco | 4,671 km | 6h 10m | SV |
| Colombo | CMB | Sri Lanka | 4,688 km | 6h 0m | SV |
| Dhaka | DAC | Bangladesh | 5,122 km | 6h 40m | SV, BG, XY |
| Sylhet | ZYL | Bangladesh | 5,242 km | 6h 48m | BG |
| Chittagong | CGP | Bangladesh | 5,301 km | 6h 30m | BG |
| Hat Yai | HDY | Thailand | 6,735 km | 8h 35m | SV |
| Kuala Lumpur | KUL | Malaysia | 7,065 km | 8h 55m | SV, MH |
| Jakarta | CGK | Indonesia | 8,002 km | 10h 0m | GA, SV |