We consider the massive Klein-Gordon equation on asymptotically Minkowski spacetimes, in the sense that the manifold is $R^{1+d}$ and the metric approaches that of Minkowski space at infinity in a short-range way (jointly in time and space variables). In this setup we define Feynman and anti-Feynman scattering data and prove the Fredholm property of the Klein-Gordon operator with the associated Atiyah-Patodi-Singer type boundary conditions at infinite times. We then construct a parametrix (with compact remainder terms) for the Fredholm problem and prove that it is also a Feynman parametrix in the sense of Duistermaat and Hörmander.