A multidimensional nonnegative matrix is called polystochastic if the sum of its entries over each line is equal to $1$. The permanent of a multidimensional matrix is the sum of products of entries over all diagonals. We prove that if $d$ is even, then the permanent of a $d$-dimensional polystochastic matrix of order $4$ is positive, and for odd $d$, we give a complete characterization of $d$-dimensional polystochastic matrices with zero permanent.