Having trouble getting all the Combat Kings? Fear not! Here is a guide.

 
Combat King 001: In a cell on the first floor of the D-District Prison
Combat King 002: Defeat Fujin and Raijin in Balamb
Combat King 003: Get from the Library Girl in Balamb
Combat King 004: Get from an Esthar Soldier in Esthar
Combat King 005: Found in Lunatic Pandora during Disc Three

NOTE: You can buy all the Combat Kings during Disc Three from the Esthar Book Store as long as you have taught Tonberry GF the Familiar ability.