The Letter to the Colossians and Philemon
The letters to the Colossians and Philemon should be considered together. Both letters are written from "Paul and Timothy" (Col 1:1, Philemon 1). The returning runaway slave Onesimus, now a believer, is the central figure in Philemon. Paul is sending him back (Philemon 12) in Philemon, and in Colossians he is also returning (Col 4:9-10). This seems to indicate that Colossians and Philemon were written and delivered together to the church in Collosse, along with a letter we no longer have to the Laodiceans (Col 4:16). Other characters appear in the same geographic location in both books: Archippus (Philemon 2, Col 4:17) is greeted, while Luke (Philemon 24, Col 4:14), Aristarchus (Philemon 24, Col 4:10), and Epaphras (Philemon 24, Col 4:12) are with Paul. Mark (Philemon 24) is also with Paul, but may come later to Colosse (Col 4:10).
Colossians is written while Paul is in prison (Col 4:10, 4:18). The bearer of the letters was apparently Tychicus (Col 4:7), and the collection of letters he was carrying probably included Ephesians (Eph 6:21-22). Mark has obviously now been reconciled with Paul, unlike the situation at the beginning of Paul's second missionary journey (Acts 15:26-31). Demas (Philemon 24) is still with Paul, though later he will "forsake" him (2 Tim 4:10). The question as to the date of the letter thus comes down to which prison - Caeserea or Rome? It is impossible to be dogmatic, but the fact that Paul has few Jewish companions (Col 4:11) seems more likely in Rome than in Caesarea, which is in the land of Israel. Also, the work and gospel of Mark is connected to Rome, and since Mark is with Paul when this letter is written, a Roman origin seems more likely. This would place the letters of Colossians and Philemon at the same time, around 61-62 A.D.