A Padé approximant scheme for realizing the discrete-time evolution of the state of a many-atom system is introduced. This temporal coarse-graining scheme accounts for the underlying Newtonian physics and avoids the need for construction of spatially coarse-grained variables. Newtonian physics is incorporated through short molecular dynamics simulations at the beginning of each of the large coarse-grained timesteps. The balance between stochastic and coherent dynamics expressed by many-atom systems is captured via incorporation of the Ito formula into a Padé approximant for the time dependence of individual atom positions over large timesteps. Since the time for a many-atom system to express a characteristic ensemble of atomic velocity fluctuations is typically short relative to the characteristic time of large-scale atomic displacements, a computationally efficient and accurate temporal coarse-graining of the atom-resolved Newtonian dynamics is formulated, denoted all-atom Padé-Ito molecular dynamics (APIMD). Evolution of the system over a time step much longer than that required for standard molecular dynamics (MD) is achieved via incorporation of information from the short MD simulations into a Padé approximant extrapolation in time. The extrapolated atomic configuration is subjected to energy minimization and, when needed, thermal equilibration so as to avoid occasional unphysical close encounters deriving from the Padé approximant extrapolation and to represent configurations appropriate for the temperature of interest. APIMD is implemented and tested via comparison with traditional MD simulations of five phenomena: (1) pertussis toxin subunit deformation, (2) structural transition in a T = 1 capsid-like structure of HPV16 L1 protein, (3) coalescence of argon nanodroplets, and structural transitions in dialanine in (4) vacuum, and (5) water. Accuracy of APIMD is demonstrated using semimicroscopic descriptors (rmsd, radius of gyration, residue-residue contact maps, and densities) and the free energy. Significant computational acceleration relative to traditional molecular dynamics is illustrated.