The historical relations of the Papuan languages scattered across the islands of the Alor archipelago, Timor, and Kisar in southeast Indonesia have remained largely conjectural. This paper makes a first step toward demonstrating that the languages of Alor and Pantar form a single genealogical group. Applying the comparative method to primary lexical data from twelve languages sampled across the islands of the Alor-Pantar archipelago, we use form-meaning pairings in basic cognate sets to establish regular sound correspondences that support the view that these languages are genetically related. We reconstruct 97 Proto-Alor-Pantar vocabulary items and propose an internal subgrouping based on shared innovations. Finally, we compare Alor-Pantar with Papuan languages of Timor and with Trans-New Guinea languages, concluding that there is no lexical evidence supporting the inclusion of Alor-Pantar languages in the Trans-New Guinea family.