Their best has been the semi-finals - in 2008 when they lost to Selangor 2-1 on aggregate -- and last year when Negri Sembilan stopped them from a historic place in the final by a similar score line.
Things look no better for club side Johor FC in this year's Malaysia Cup which kicks-off on Sept 6, having been drawn with defending champions Kelantan, who have established themselves as the new powerhouse in the game in the country.
Kelantan are also the reigning Super League champions and Charity Cup holders.
The other teams in Group C are Felda United, who are rich in experience and coached by E. Elavarasan, and newly promoted Sarawak, who are helmed by the wily Dutchman Robert Alberts, a former national coach.
Inconsistency has been Johor FC's main fault and this was seen in the Super League when they plunged to a lowly seventh after a fourth place last year and third in 2009.
And Johor FC's poor showing in the pre-Malaysia Cup friendlies have not drawn any encouraging results so far.
The most embarrassing was the 4-0 defeat to Johor, who play in the lower Premier League, a 1-1 draw against Negri and a 3-1 beating at the hands of Selangor, are statistics that are cause for concern.
Club president Ahamad Mohamad drove home the message when he said the team "lack a good motivator and leader" when voicing his disappointment with the team's management and coach Azuan Zain.
Johor FC secretary Tahir Hamdan, however, was more accommodating and said that the results of the friendly matches must be taken with a "pinch of salt".
"These are just warm-up matches as the coach tries out his match plans ahead of a tough competition like the Malaysia Cup. I believe that Johor FC will be able to hold their own against the challengers for a place in the quarter-finals," said Tahir.
"Kelantan look too strong and have the credentials to go far in the Malaysia Cup this season. After all they are the best football team in the country now. The second slot for a quarter-final berth is a battle between Felda, Sarawak and Johor FC.
"We have played Felda in the league and know their capabilities. They have an experienced team and the players to ride on while Sarawak are an unknown quality. However, the fact that they have earned promotion to the Super League speaks of their ability to stretch us."
Johor FC were again slow when coming to sign players who could have given the team more depth and plug the loopholes upfront.
Instead, Johor settled for another defender - Saiful Nizam Miswan from Pahang.
The club, who have never failed to qualify for the Malaysia Cup, have been struggling to get their act together upfront with former international Eddie Helmi Abdul Manan, national trainee Shahrizal Saad, signed from Perak this season, and Azizan Baba, all struggling to find the net.