The notion earlier in Revelation is that Satan is already residing on the earth (cf. 12:12-13):
"I know where you live [the city of Pergamum] -- where Satan has his throne. Yet you remain true to my name. You did not renounce your faith in me, even in the days of Antipas, my faithful witness, who was put to death in your city -- where Satan himself lives" (Revelation 2:13).
Similarly, if you compare 13:2 with 17:9-11, it is clear that from the writer's standpoint the Beast (which the Dragon delegates his authority to AFTER having been cast out of heaven) has already been around for some time (namely, the six kings or emperors that have fallen), while one of the former kings was due to return after the present king (i.e. the head of the Beast that was killed and then healed, in 13:2).
Beyond that, it is hard to say because the NT texts vary on this matter. Revelation 17 would imply sometime prior to Julius or Augustus Caesar (depending on who was considered the first of the seven kings), while Revelation 12 would point to the time of Jesus' birth (if indeed it does have such an interpretation; this is debatable). The logion in Luke 10:18 suggests that Satan's fall has already occurred ("I saw Satan fall like lightening from heaven") for this author, while the Johannine texts point to the time of Jesus' crucifixion and resurrection as the time Satan was defeated (cf. John 12:31-32, 14:30, 16:11, 33), which also has parallels with Pauline and sub-Pauline texts about the humiliation of the archons, principalities and powers (cf. Philippians 2:7-10, Colossians 1:19-20, 2:14-15, Ephesians 1:20-23; cf. 1 Peter 3:21-22).
Papias of Hierapolis (c. AD 140) gave the earliest known interpretation of Revelation 12, and described the "war" as one that has occurred throughout all of human history since Creation, with Michael and his legions giving the Mosaic Law to Israel to fight the Devil and his temptations, but Satan was not completely defeated until Christ came, fulfulling the Law in his body and who "defeated sin and condemned Satan, and through his death he spread abroad his righteousness over all. As this occurred, the victory of Michael and his legions, the guardians of mankind, became complete, and the dragon could resist no more, because the death of Christ exposed him to ridicule and threw him to earth" (Fr. 24, cited by Andrew of Caesarea).