カエナグナトゥスの分類をめぐっては複雑な歴史がある。1936年に一組の顎の化石が発見され、カエナグナトゥスと命名された。この名は「最近の顎」を意味し、最初は鳥の顎であると考えられたためである[3]。1988年、1923年から保管されたままであったある標本が発見され、研究が行われた。この化石は慣習的にいくつかの断片的なオヴィラプトロサウルス類の種と関連付けされて、単一の属キロステノテスに帰属された。この属は最初一組の手の骨に基づいて記載されたものであり、この化石は長らくカエナグナトゥスと同じ動物に由来するものと考えられていた。これらの化石に対して最初に適用された名前はキロステノテスであったため、長きに渡ってキロステノテスのみが正当な名前として認識されてきた[4]。しかし研究の進展と、カエナグナトゥス類のより完全な骨格化石も発見により、これらの化石が同じ種に属しているという考えには疑義が生じるようになった。複数の研究からキロステノテスは派生的なオヴィラプトロサウルス類であり、オヴィラプトル科（英語版）に属する可能性が高く、カエナグナトゥスはより原始的な種であることが示唆された[5]。
カエナグナトゥス属の地位と他のカエナグナトゥス科に属するオヴィラプトロサウルス類との関係についての問題は2014年と2015年に発見されたより完璧な標本により解決されつつある。2014年に記載されたアンズー・ウィリエイはカエナグナトゥス科としては初めての完全に近い骨格であり、今まで発見されていたより断片的なカエナグナトゥス科の標本間の差異を明らかにする手助けとなった。系統解析の結果、C. collinsi はキロステノテスよりもアンズーに近縁であることが分かった。また2014年の解析では以前にはカエナグナトゥス属の第2の種とされていた"Caenagnathus" sternbergi がアンズーとカエナグナトゥスからなるグループの姉妹群であることが分かった[6]。2015年にはC. collinsi の新たな化石が発見された。この標本は大きさおよび解剖学的な特徴がより小型のキロステノテスとより大型なアンズーの中間的な状態であり、上記の系統仮説を支持するものであった。この標本は四肢、特に手と中足骨の特徴でキロステノテスおよび同時代に生息したレプトリンコスと識別可能である[2]
下記に示すクラドグラムは Lamanna et al. 2014をの解析を元にカエナグトゥス科の系統関係を示したものである[6]
