본관, 출신과 가계 등은 기록에 전하지 않아 자세히 알 수 없다. 1216년(고종 3) 대장군(大將軍)으로서 동계겸춘주도방호사(東界兼春州道防護使)에 임명되었다. 최유공은 당시 몽고군에게 밀려 고려 영토로 침입한 거란유종(契丹遺種)의 남하를 차단, 지연시키기 위한 방어임무를 수행하였다. 이후 정의대부 흥위위 상장군 판대부사(正議大夫 興威衛 上將軍 判大府事)에 올랐다.
1217년(고종 4) 최유공은 총사령관 김취려(金就礪)가 이끄는 고려 삼군 중 좌군(左軍)의 지병마사(知兵馬事)가 되었다. 그리고 이 해 서경병마사(西京兵馬使) 상장군(上將軍)이 되어, 판관(判官) 예부낭중(禮部郞中)인 김성(金成) 등과 함께 서경 병력으로 정부군을 구원하는 임무를 맡았다. 그런데 군졸(軍卒) 최광수(崔光秀)가 서경(西京)에서 고려왕조를 부정하며 고구려부흥운동을 일으켰다. 이 사건은 최유공이 평상시 사졸들을 착취한 것을 빌미로 해서 발발했는데, 이 사건에 제대로 대처하지 못해 여론의 비난을 받았다.
1223년(고종 10) 최유공은 추밀원부사 오수기(吳壽祺), 장군 김계봉(金季鳳), 낭장(郎將) 고수겸(高守謙) 등과 함께, 중방(重房)의 장군들을 초빙해서 최우(崔瑀)의 신임을 받던 문신들을 모두 죽이려는 음모에 가담했다. 그러나 이 일이 사전에 발각되어 거제현령(巨濟縣令)으로 좌천되었다. 이에 불만을 품은 최유공은 1224년(고종 11) 대장군 이극인(李克仁), 장군 김계봉 등과 함께 무신권력자 최우를 살해하려 하였으나 실패하여 죽음을 당하고 말았다.