In the current debate concerning Paul and Empire, much of the discussion situates Paul’s language in contrast to the imposition of Roman imperial ideology (especially through the emperor cult). Since Paul does not explicitly mention Caesar in his letters, the analysis of his anti-imperial rhetoric is shown primarily from implicit meanings of key terminology (e.g., euangelion, kyrios, pistis, dikaiosyne, eirene, etc.), often drawn out by recourse to post-colonial criticism and Scott’s hidden transcripts. However, there has been no sustained discussion of the earliest non-canonical biography of Paul which sets his martyrdom explicitly in an anti-imperial context. As a result, this paper will consider what light Paul’s interaction with Nero as expressed in The Acts of Paul (AP)—a second century account of Paul’s life, ministry, and death—sheds on the debate about Paul and Empire. In this account Nero’s anger is provoked as a result of the following central themes: Christ is the ‘king’ (basileus) who will destroy all other ‘kingdoms’ (basileiai), and believers as ‘soldiers’ (stratiotai) who serve in his army. This type of language appears infrequently in Paul’s undisputed letters, though it has some affinity with the Pastorals. Accordingly, I argue that although the church held in its memory that Paul’s message stood in contrast to imperial ideology, the AP did not find his undisputed letters particularly important for documenting his supposed anti-imperial rhetoric. As a result, the author may not have considered the anti-imperial language to be as transparent as many scholars argue today.