This paper is devoted to the description and validation of a new implementation of a fourth-order space-time conservation-element and solution-element (CESE) scheme to numerically solve the time-dependent, three-dimensional (3D) magnetohydrodynamic (MHD) equations. The core of the scheme is that, with the aid of a grid staggered in space and time, the conservative variables are advanced by integration of the controlling equation in the space-time four-dimensional domain by utilizing Taylor expansion, and their spatial derivatives are computed by finite difference with $p$ order derivatives from $p-1$ order ones. The new scheme achieves fourth-order accuracy in both space and time simultaneously, using a compact stencil identical to that in the second-order CESE scheme. We provide a general framework for convenience of programming such that the scheme can be easily extended to arbitrarily higher order by including higher-order terms in the Taylor series. A suite of 3D MHD tests demonstrate that the fourth-order CESE scheme at relatively low grid resolutions can obtain reliable solution comparable to the second-order CESE scheme at four-times high resolution, and showing a very high efficiency in computing by using only around $5%$ of the computing resources.