Disclosed are various embodiments for fast and accurate identification of message-based application programming interface (API) calls in Objective-C binaries. An application binary is analyzed to determine a first listing of classes and a first listing of methods. Metadata is extracted from the application to determine a second listing of classes and a second listing of methods. A listing of external classes and a listing of external methods are determined. Data identifying public API definitions is obtained. Public APIs invoked by the application are determined by comparing the external classes and methods with the public API definitions.