The arrow paradox is an argument purported to show that objects do not really move. The two main metaphysics of motion, the At–At theory of motion and velocity primitivism, solve the paradox differently. It is argued that neither solution is completely satisfactory. In particular it is contended that there are no decisive arguments in favor of the claim that velocity as it is constructed in the At–At theory is a truly instantaneous property, which is a crucial assumption to solve the paradox. If so the At–At theory faces the threat that most of our physical theories turn out to be non-Markovian. Finally it is considered whether all those threats and paradoxes are dispelled if only a new metaphysics of persistence is taken into account, namely four-dimensionalism.