The answer is no. Here is a counter-example
$$\left( \begin{matrix} 0 & -5 \\\\ 1 & 0 \end{matrix} \right) \quad \mbox{and} \quad \left( \begin{matrix} -1 & -3 \\\\ 2 & 1 \end{matrix} \right).$$

Both of these matrices have characteristic polynomial $x^2+5$. For $p \neq 2$, $5$, this polynomial has no repeated factors so any matrices with this polynomial are similar. By the same argument, they are similar over $\mathbb{Q}$. By brute force computation, they are also similar at $2$ and $5$.

However, they are not similar over $\mathbb{Z}$. Consider $\mathbb{Z}^2$ as a module for $\mathbb{Z}[t]$ where $t$ acts by one of the two matrices above. Both of these matrices square to $-5$, so these are in fact $\mathbb{Z}[\sqrt{-5}]$-modules. If the matrices were similar, the similarity would give an isomorphism of $\mathbb{Z}[\sqrt{-5}]$-modules. But these are not isomorphic: the former is free on one generator while the latter is isomorphic to the ideal $\langle 2, 1+ \sqrt{-5} \rangle$.

In general, the way to classify similarity of matrices over $\mathbb{Z}$ is the following: If the matrices do not have the same characteristic polynomial over $\mathbb{Q}$, they are not similar. If they do, let $f$ be the characteristic polynomial and let $R=\mathbb{Z}[t]/f(t)$. Then your matrices give $R$-modules, and the matrices are similar if and only if the $R$-modules are isomorphic. If $R$ is the ring of integers of a number field, then $R$-modules are classified by the ideal class group. In general, they are related to the ideal class group, but there are various correction factors related to how $R$ fails to be the ring of integers of its fraction field (or how it fails to be a domain at all). I don't know the details here.