In this study, a multi-objective optimization regarding the tribological characteristics of the hybrid composite with a base material of aluminum alloy A356 as a constituent, reinforced with a 10 wt.% of silicon carbide (SiC), size 39 µm, and 1, 3, and 5 wt.% graphite (Gr), size 35 µm, was performed using the Taguchi method, gray relational analysis (GRA), and Technique for Order Preference by Similarity to Ideal Solution (TOPSIS) decision-making methods. Tribological tests were carried out on a “block on disc” type tribometer with lubrication. Load, sliding speed, and graphite mass concentration were analyzed as input parameters. As output parameters, wear rate and coefficient of friction were calculated. An analysis of variance (ANOVA) was conducted to identify all parameters that have a significant influence on the output multi-response. It was found that the normal load has the highest influence of 41.86%, followed by sliding speed at 32.48% and graphite addition at 18.47%, on the tribological characteristics of composites. Multi-objective optimization determined that the minimal wear rate and coefficient of friction are obtained when the load is 40 N, the sliding speed is 1 m/s, and the composite contains 3 wt.% Gr. The optimal combination of parameters achieved by GRA was also confirmed by the TOPSIS method, which indicates that both methods can be used with high reliability to optimize the tribological characteristics. The analysis of worn surfaces using scanning electron microscopy revealed adhesive and delamination wear as dominant mechanisms.