The quantum time of arrival (TOA) problem requires the statistics of measured arrival times given only the initial state of a particle. Following the standard framework of quantum theory, the problem translates into finding an appropriate quantum image of the classical arrival time $\mathcal{T}_C(q,p)$, usually in operator form $\hat{\mathrm{T}}$. In this paper, we consider the problem anew within the phase space formulation of quantum mechanics. The resulting quantum image is a real-valued and time-reversal symmetric function $\mathcal{T}_M(q,p)$ in formal series of $\hbar^2$ with the classical arrival time as the leading term. It is obtained directly from the Moyal bracket relation with the system Hamiltonian and is hence interpreted as a Moyal deformation of the classical TOA. We investigate its properties and discuss how it bypasses the known obstructions to quantization by showing the isomorphism between $\mathcal{T}_M(q,p)$ and the rigged Hilbert space TOA operator constructed in [Eur. Phys. J. Plus \textbf{138}, 153 (2023)] which always satisfy the time-energy canonical commutation relation (TECCR) for arbitrary analytic potentials. We then examine TOA problems for a free particle and a quartic oscillator potential as examples.