In order to investigate the microscopic magnetic nature of a sodium phospho-olivine, we have measured μ+SR spectra for NaxFePO4 using a powder sample in the temperature range between 2 and 500 K. ZF-μ+SR measurements below 200 K at TRIUMF showed the appearance of static magnetic order below TN= 61 K, where the susceptibility-vs.-temperature curve exhibits a sharp maximum due to an antiferromagnetic (AF) transition. The wide distribution found for the internal magnetic field (Hint) was explained by the formation of AF order with the spread in Hint due to random distribution of Na vacancies. At higher temperatures, the ZF-spectrum for Na0.7FePO4, obtained at J-PARC, is found to change from a low-T static behavior to a high-T dynamic behavior above 300 K. This is consistent with the fact that Na+ ions are reversibly extracted from and intercalated into the NaxFePO4 lattice, while there is no NMR study on Na-diffusion in NaxFePO4 due to large Fe moments.