The hydrogenolysis reactions of Muswellbrook coal liquefaction residue (CLR) and triaromatic azaarenes related to the basic coal liquid were investigated by using red mud and sulfur catalysts. In the reaction of CLR and benzo[f]quinoline, the conversion of CLR to dichloromethane soluble was depressed. The upgrading of CLR was slightly enhanced in the reaction of CLR and acridine. In the reaction of CLR and phenanthridine, the hydrogenolysis of CLR to dichloromethane soluble facilitated; however, the upgrading to n-hexane soluble was depressed. In the reaction of CLR and benzo[h]quinoline, since benzo[h]quinoline dissolved and dispersed CLR, upgrading of the mixture occurred effectively by the catalyst poisoned little for heterocycle moiety of benzo[h]quinoline. Therefore, the upgrading of CLR was enhanced by the solvent effects of benzo[h]quinoline. In the reaction of CLR and basic fraction separated from Muswellbrook coal liquid, the synergistic effects to upgrading, such as the increase of n-hexane soluble and the decrease of dichloromethane insoluble, have been observed. Consequently, it was considered that the upgrading of CLR was facilitated by the compounds having the skeleton structure similar to benzo[h]quinoline and phenanthridine in the basic fraction.