This article examines ways in which Paul defined the notion of apostleship in the course of conflict with rival authority claimants in the early Church. In Galatians Paul defines and asserts his apostolic self-identity in order to regain the oversight of the Galatian churches which he had previously exercised as an apostle of the church of Antioch. In 2 Corinthians Paul asserts his authority as church founder against rivals who recognise no territorial jurisdiction. No common agenda, theological position, or conception of apostleship can be identified. Rather, rival authority claimants based their legitimacy on different criteria in different situations.