Al Shorta were invited to take part in the 2004 Algomhuria International Cup, which was to be hosted in Alexandria in Egypt in August 2004. Participating in this tournament were eight teams, meaning that the format of the tournament was two groups of four, with the winner of each group playing in the final and the second-placed team of each group facing off in a third-place playoff. Group A consisted of Al Zamalek, Al Shorta, Al Sharjah and Al Shabab, whilst Group B included Al Olymbiy, Al Ittihad Al Sakandary, Al Akhdhar and Al Ansar.
Al Shorta, donning a purple strip, kicked off their tournament against the favourites of the competition, Egyptian club Al Zamalek. Most people expected Al Shorta to lose the game, but they drew 1-1. Ahmad Saleh opened the scoring for Al Zamalek just two minutes into the tie and many expected more goals to come. But thirteen minutes later, Ammar Abdulhussein equalised with a great penalty that was won by Hashim Ridha. Al Shorta missed a one-on-one chance but were still controlling the midfield; their defence was very solid, especially with Maher Habeeb playing at his best. Maher and Al Shorta's 'keeper were saving their team with some fine tackles and saves. Up front, Tassyer Abdulhussein and Hashim Ridha were looking very deadly, but near the end of the match Al Shorta had to defend to keep the draw which they did very well. Most fans agreed that it was a great result for Al Shorta.
Al Shorta's next game was against the worst side in the tournament, Kuwaiti club Al Shabab. Because Al Zamalek drew their game against Al Sharjah, Al Shorta would go to the top of the group with a win here. And they did win very comfortably with a 4-0 demolition of Al Shabab. Legendary striker Hashim Ridha scored the first two goals of the game in the 12th and 40th minutes, with Haitham Kadhem making it 3-0 on 47 minutes. Forward Bashar Saad completed the rout with the fourth and final goal on 78 minutes to put Al Shorta top of Group A.
Al Shorta's final group game was against Al Sharjah of the United Arab Emirates. Al Zamalek had defeated Al Shabab 7-0, meaning that Al Shorta had to defeat Al Sharjah to reach the final. A loss would see them finish one point behind Al Zamalek, whereas a draw would see them finish behind Al Zamalek on goal difference, so they had to win. Al Sharjah took the lead against the Police and it was 1-0 to them at half-time. Al Shorta weren't playing too well at this point, but they gradually improved and equalised on 73 minutes through Ammar Abdulhussein's goal. Al Sharjah took the lead once more leaving Al Shorta with the difficult task of having to score two goals to reach the final. Al Shorta did score an equaliser in the 94th minute of the match through Ammar Ahmad, but it was too late to win the game and the result meant that Al Shorta were to play in the third-place playoff. Al Shorta's manager Younis Abid Ali was pictured crying on the pitch, which showed how much he cared about the club and how passionate he was.
Group A ended with Al Zamalek in first place with five points and +7 goal difference. Al Shorta were in second with five points and +4 goal difference, and Al Sharjah finished third with five points and +3 goal difference. Al Shabab were bottom with no goals scored and fourteen conceded. Group B finished with Egyptian team Al Olymbiy at the top with seven points, and Egyptian club Al Ittihad Al Sakandary in second with four points. Libyan club Al Akhdhar finished in third with three points and -2 goal difference, with Saudi Arabian side Al Ansar finishing bottom with three points and -3 goal difference.
This meant that Al Shorta were to face Al Ittihad Al Sakandary in the third-place playoff. After an exhilarating match that ended 3-3 after extra time, there was a penalty shootout to decide who would finish in third place. Unfortunately for the Police, they were defeated 6-4 in the shootout and they had finished in fourth place in the tournament. The eventual winners of the tournament were Al Zamalek, who beat Al Olymbiy 3-2 in the final. The player of the tournament was Al Shorta's Iraqi player Haitham Kadhem, who most pundits and fans agreed deserved his award.
Al Shorta didn't win the tournament, but it certainly made Al Shorta and their players more recognised in Asia, and especially Egypt, who hosted the tournament. Egyptian clubs were reportedly interested in some Al Shorta players after the competition, with rumours at the time suggesting that Hashim Ridha was wanted by Al Ahly, Maher Habeeb was wanted by Al Terasanah and Tassyer Abdulhussein was wanted by ENPPI. It was a good tournament for Al Shorta overall, and a fourth place finish was very respectable.