公長の出自は明らかでないが、大きく分けて二つの説が存在する。一つは天慶の乱で藤原純友を討伐した橘遠保の子孫とする説で、遠保から公長へと繋げる系図もある。もう一つは中央貴族橘氏の子孫とするもので、参議･橘好古の孫である橘則光の子･季通の玄孫とされる。
　弓馬と知謀に優れ、元々平知盛の家人であったが、治承4年(1180年)12月に平家を見限り、同僚であった加々美長清の仲介で源頼朝の麾下に入る。粟田口で当時源為義の家人であった斎藤実盛と片切景重と喧嘩になった際、頼朝の祖父･源為義が朝廷に訴えず斎藤,片切を諫めたことから、公長は源家への恩を忘れず、縁者を訪ねて遠江国に下向し、鎌倉へ向かったという。
　源義経の下で戦い、元暦2年(1185年)の壇ノ浦の戦い後、捕虜となった平家の総帥･平宗盛の処刑を担当し、そのことと平重衡の最期について鎌倉の頼朝に報告した。『平家物語』によると、世の人々は公長がかつて平家の家人であったことを忘れておらず、その変わり身に多くの批判を浴びせたという。