This paper proposes a new fuzzy case-based reasoning system In which fuzzy rule-based reasoning is utilized as a mechanism for matching between cases. The motivation is that fuzzy if-then rules present a more powerful and flexible means to represent the knowledge about case relevance than traditional distance based similarity measurements. With such fuzzy rules available, every case in the case base can be examined via fuzzy reasoning to predict whether it is relevant to a target problem in query. Those cases that are predicted as relevant are then retrieved and delivered to the next stage of decision fusion. Further, we claim that the set of fuzzy rules for case relevance prediction can be learned from the case base. The key to this is doing pair-wise comparisons of cases with known solutions In the case base such that sufficient samples of case relevance can be derived for fuzzy rule learning. The evaluations conducted on a benchmark data set have shown that the fuzzy rules in demand can be learned from a rather small case base without the risk of over-fitting and that the proposed system yields high information recall rate by capturing more cases that are relevant while not undermining the precision for the set of retrieved cases.