I had a theory awhile back (and I think others had mentioned stuff on it before also) that King was the former Warden of Impel Down, and helped Kaido escape captivity. We know prior to Luffy and Co, only Shiki had ever escaped Impel Down, but it could just be a case of the WG covering it up. It'd be a huge blow to their image if word got out that the Warden of Impel Down helped a prisoner escape, and became his subordinate.