Al Nasr made their second consecutive appearance in the AFC Champions League in 2013 but finished bottom of the group with only one point.
In 2016 Al Nasr qualified for the third time after winning the president's cup, the club would pull a surprise 2–1 victory against Saudi giants Al-Ittihad to qualify for the Round of 16 of the AFC Champions League for the first time, they later faced Iranian team Tractor Sazi who topped their group.
Al Nasr pulled an upset as they won 4–1[1] against the Iranians in the first leg, and only losing 1–3 in the second, the team qualified for the quarter-finals for the first time.
The team would later face Qatari side, El Jaish, they won 3–0 on the first leg however unfortunate events hit the club as they fielded the player Wanderley, who was found to be registered using a fake Indonesian passport.
They qualified again in 2019 after finishing fourth in the league but were defeated in the playoff game to the Uzbek side Pakhtakor.