Catalytic hydrodesulfurization (HDS) plays an important role in the conversion of sulfur-laden residual oils. Cobalt molybdate catalysts are commonly used for the process. In the present study, a series of alumina-aluminum phosphates (AAP) was prepared by a precipitation technique. These materials were used as a support of CoMo HDS catalysts. The samples were characterized by X-ray diffraction, BET surface area, and mercury-penetration pore volume measurements. The temperature-programmed reduction method was used to monitor the reducibility of MoO2. HDS of Kuwait atmospheric residuum over these catalysts was carried out in a cocurrent down-flow trickle bed reactor at 663 K and 7582 kPa. The reaction data can be fitted very well with a pseudo-second-order rate equation. The activation energy is 29 kcal/mol. A correlation exists between the reducibility of the oxidic precursor and the HDS activity of the sulfided samples. The higher the reducibility of the oxidic samples, the higher the HDS activity of the sulfided samples. Larger surface area, smaller acid amount, and weaker interaction of AAP supports make the metal more highly disperse, produce more active sites, and result in a high initial HDS activity.