I initially regarded Colossians as being written by Paul from Rome, but have now changed my mind and gone with an Ephesian provenance. Here's the discussion that led me to that conclusion:
Given the qualified assumption of Pauline authorship of Philemon, Colossians, and (more loosely) Ephesians, when and where were the former two epistles written? What we can say is that Colossians and Philemon were probably written in relatively close temporal proximity to each other because five identical persons are mentioned in Paul’s greetings in both letters, namely, Luke, Mark, Demas, Aristarchus, and Epaphras (Col. 4.10-14/Philm. 24). Timothy is named as co-author in both letters (Col. 1.1/Philm. 1) and Onesimus is associated with both letters as well (Col. 4.9/Philm. 10). One peculiar fact is that Colossians makes no reference to any potential conflict between Onesimus and Philemon which one might expect on the return of a runaway slave to his owner which could adversely affect relations within the community (see Paul’s exhortation for unity and reconciliation among Euodia and Syntyche in Phil. 4.2). In Col. 4.9, Onesimus is also regarded as a faithful and experienced co-worker. It would seem that there was a gap between the composition of Philemon and Colossians. I surmise that Paul sent Onesimus back to Philemon. Philemon was reconciled to Onesimus and subsequently returned Onesimus to Paul’s service as requested by Paul. Sometime later, the news of an encounter with a certain ‘philosophy’ in Colossae was relayed to Paul and his co-workers who responded by writing Colossians and sending Tychicus and Onesimus to deliver the letter to Colossae and a circular letter (Ephesians) to the other churches of Asia. I find this scenario plausible, though admittedly unprovable.
So where was Paul when this happened, obviously in captivity (Philm. 1, 10, 23; Col. 4.3, 10, 18), but which period of captivity, he refers to imprisonments in the plural in 2 Cor. 11.23. The main candidates are Ephesus (ca. 54-57) or Rome (ca. 61-66). This subject is one of the most perplexing ones facing students of Colossians. The problem is mirrored in text-critical observations since some manuscripts (A, B, P) regard Colossians as written from Rome, while the Marcionite prologue declares it written from Ephesus. Even if we take into account the movements of Paul’s co-workers according to the Pauline letters and the Book of Acts, the evidence still remains ambiguous. The internal evidence of Colossians and Philemon themselves does not help us, nor does taking into account the wider New Testament provide us with a clear cut answer. Instead, we have to weigh the arguments for and against an Ephesian or Roman setting.
Roman Setting. In favour of a Roman provenance is that we know that Paul did experience a prolonged period of imprisonment in Rome which is attested by Acts (Acts 28.16) and other early Christian literature. The Pastoral Epistles (if authentic) also testify to a Roman imprisonment (2 Tim. 1.17) and perhaps Philippians as well but as we will see the provenance of Philippians is contestable (Phil. 1.13-14). But there is no clear reference to a Roman imprisonment in the undisputed letters of Paul, which is no small fact, and must be taken into consideration. Second, in Philemon 9, Paul calls himself an ‘old man’ which suggests that it was written the end of his life. However, this might be a phrase used rhetorically to get Philemon to respect his elder and the apostle and life expectancy rates in the ancient world were much lower than the present so what constitutes ‘old’ might even encompass someone in their forties. Third, and perhaps the strongest argument for a Roman provenance, is that the theology of Colossians seems to represent a maturation and development of Pauline thought. This is attributable no doubt to Paul’s own theological reflection on christology and ecclesiology, but also to the interpretation of Paul’s thought that began with his co-workers like Timothy and has already begun to weave it’s way into the letter. Still, this does not necessitate a later date since Paul’s theology clearly developed somewhat during the short time span between Galatians (ca. 49 AD) and Romans (ca. 55-56 AD) and we do not know how much of the so-called developed theology of Colossians is attributable to the interpretive insights of Paul’s co-workers and their inferences about Paul’s theology which could have been made from any location or residence with time for writing and reflection. Fourth, the statements in Col. 1.6, 23 that the gospel is bearing fruit all over the world and has been proclaimed to every creature under heaven is more consistent with a Roman setting, since Rome was the centre of the political world, whereas Paul’s visits to Ephesus were still connected to his mission in and around the Aegean. When Paul wrote Romans from Corinth ca. 55-56 AD, he had finished his ministry in the east ‘from Jerusalem all the way around to Illyricum’ (Rom. 15.19), but did not describe it as a ministry that had touched ‘all over the world’ or ‘every creatures under heaven’. Then again, even in Rome, Paul had yet to fulfil his ambition to go to Spain (Rom. 15.24, 28) which meant that that part of the world was still left evangelized. So Col. 1.6, 23 may be no more than a generalizing statement or a piece of hyperbolic evangelicalism on the progress of the gospel in various quarters of the Roman Empire. Fifth, Rome would be a very good place for a runaway slave to hide in the massive population of the city, yet it was also a heck of a long way to travel (approximately 1200 miles by sea) when other cities in Asia Minor and Syria such as Ephesus and Antioch were nearer and large enough to afford a veil of protection. Sixth, a Roman setting was the preferred view of patristic authors, but it was not unamious, and constitutes tertiary evidence at best.
Ephesian setting. The case for an Ephesian setting is strengthed by accounts which place Paul there more than once (1 Cor. 16.8; Acts 18.19-21 and esp. 19.1-20.1) and for three years during his third missionary journey (Acts 19.8-10; 20.31). That Paul experienced imprisonment in Ephesus is arguably implied in 2 Cor. 1.8 where the apostle refers to the hardships experienced by he and his companions in Asia and 1 Cor. 15.32 where Paul speaks of fighting wild beasts in Ephesus. However, there is no clear evidence for an Ephesian imprisonment in Paul’s letters or in Acts. Second, it can be argued that Ephesus and Colossae, only 100 miles apart, make the flight of Onesimus, the delegation of Tychicus/Onesimus, any travels back and forth by Epaphras, the forthcoming visit of John Mark, and the possible visit of Paul to Philemon far more plausible. This flurry of comings and goings is more likely than a series of length sea journeys that were dangerous and took months at a time. Third, Paul’s request in Philm. 22 that a guest room be prepared for him is more realistic given an Ephesian imprisonment. If it was Paul’s plan to go further west after his release from confinement in Rome, then a journey to Colossae to visit Philemon would have meant significantly revizing (or reversing) that plan. Alternatively, the remark may simply be rhetorical and a polite wish to visit but with no intent to actually do so (my in-laws in Australia threaten to visit me in Scotland all the time but [thankfully] only rarely do so). Fourth, according to ancient sources there was an earthquake that destroyed parts of the Lycus valley especially Laodicea during ca. 60-61. Although Colossae was rebuilt without assistance we do not hear of any reference to Christians there again and only Laodicea is mentioned among the seven churches that John the Seer wrote to (Rev. 1.11; 3.14). Even so, we do not know for sure how the Christians in Colossae were affected by the earthquake and what impact it had upon their lives. True, Paul does not mention the earthquake when we might expect him to do so, but neither does he mention other ‘seismic’ events such as the expulsion of Jews from Rome under Claudius (49 AD) and their return under Nero (54 AD) when he wrote to the Romans.
The evidence is tightly balanced (and I confess to having changed my mind a number of times). The answer, I think, lies not with internal evidence from Colossians or Philemon, but with the letter to the Philippians and the movements of Timothy. Timothy is named as co-sender of Colossians and Philemon (Col. 1.1; Philm. 1). To that we can add the observations that Timothy is also named as co-sender of Philippians (Phil. 1.1), Philippians is also writen from captivity (Phil. 1.13-14), and that Philippians is similar to Philemon in at least two other respects: both look forward to Paul’s eventual release from prison (Philm. 22 and Phil. 1.19-26; 2.24) and several the stylistic similarities noted by Francis Watson. By way of deduction, my line of reasoning runs Timothy → Philippians → Philemon → Colossians → Location! Thus, the circumstances of Philippians and Timothy are crucial for the provenance and date of Colossians/Philemon. Philippians could have been written from either Rome or Ephesus too, this might sound like back to square one, but the internal and external evidence is better. There is a reference to the ‘praetorian guard’ in Phil. 1.13 which may denote the elite body guard unit of the Emperor in Rome who also functioned as a police force in the capital. There is also a reference to a greeting from those of ‘Caesar’s household’ in Phil. 4.22 which would naturally fit a Roman setting. However, ‘praetorian’ can mean more generally ‘palace guard’ or ‘military headquarters’ (Mt. 27.27; Mk. 15.16; Jn. 18.28, 33; 19.9; Acts 23.35). And ‘Caesar’s household’ might denote the imperial staff stationed at an imperial residence in Ephesus since Ephesus was also the Roman capital of western Asia. It is also unlikely that Roman prisoners would be incarcerated in the Emperor’s own residence. Furthermore, there is no reference to Timothy accompanying Paul to Rome in Acts 28, but he is placed in Ephesus during Paul’s extended ministry there (1 Cor. 16.8-10). We also know from Acts that Timothy engaged in one or more trips to Greece and Macedonia from Ephesus (Acts 19.22). Thus, Paul’s intent to send Timothy to Philippi (Phil. 2.19) is more likely to comport with his travellings to Greece and Macedonia during Paul’s stay in Ephesus than during Paul’s imprisonment in Rome. Moreover, 1-2 Timothy, though perhaps stemming from a second Roman imprisonment, places Timothy in Ephesus (1 Tim. 1.3). Timothy was asked to join Paul in Rome because Demas had deserted him and Tychicus had been sent to Ephesus, meaning that even if Timothy got to Rome, Demas and Tychichus would not be there to send their greetings during the composition of Philemon and Colossians, which rules out their composition during the later stages of Paul’s imprisonment (2 Tim. 4.9-13).As I see it, this is how it all stands:
For Rome:
1. There is a strong possibility that Philippians was written in Rome and, if so, Timothy’s presence with Paul in Rome can be verified and then linked with the letters to Philemon and to the Colossians.
2. The theology of Colossians appears to be ‘developed’ in some sense.
3. There is no clear reference to an Ephesian imprisonment and it is hard to place John Mark in Ephesus.
For Ephesus:
1. An Ephesian setting for Philippians remains plausible.
2. There is no clear reference to Timothy in Rome during Paul’s imprisonment there, but we can place him easily in Ephesus.
3. An imprisonment in Ephesus makes for a more plausible scenario regarding the movements of Onesimus and others to and from Colossae.
4. Colossae may have been destroyed in 61-62 AD.
The marginally less problematic of these options then is the Ephesian provenance. I surmize that the epistle to Philemon was written by Paul himself during an imprisonment in Ephesus ca. 54-55 AD and Philemon subsequently discharged Onesimus to Paul’s service where he became thereafter part of Paul’s entourage. Colossians was written co-operatively by Paul and his co-workers (Col. 1.1; 4.7-17) from Ephesus ca. 54-56 AD and was delivered by Tychichus and Onesimus (Onesimus a natural choice as coming from Colossae). Ephesians was written by a secretary of Paul at Paul’s behest and composed on the basis of Colossians in order to be given to the Pauline churches of Asia Minor, including Ephesus and Laodicea, as the letter carriers passed through those regions on their way to deliver the correspondence to Colossae. In editorial language, Paul is the author of Philemon, the managing editor and chief contributor to Colossians, and the commissioning editor of Ephesians.