GaTa$_4$Se$_8$ belongs to the lacunar spinel family. Its crystal structures is still a puzzle though there have been intensive studies on its novel properties, such as the Mott insulator phase and superconductivity under pressure. In this work, we investigate its phonon spectra through first-principle calculations and proposed it most probably has crystal structure phase transition, which is consistent with several experimental observations. For the prototype lacunar spinel with cubic symmetry of space group $Fbar{4}3m$, its phonon spectra have three soft modes in the whole Brillouin zone, indicating the strong dynamical instability of such crystal structure. In order to find the dynamically stable crystal structure, further calculations indicate two new structures of GaTa$_4$Se$_8$, corresponding to $R3m$ and $Pbar{4}2_{1}m$, verifying that at the ambient pressure, there does exist structure phase transition of GaTa$_4$Se$_8$ from $Fbar{4}3m$ to other structures when the temperature is lowered. We also performed electronic structure calculation for $R3m$ and $Pbar{4}2_{1}m$ structure, showing that $Pbar{4}2_{1}m$ structure GaTa$_4$Se$_8$ is band insulator, and obtained Mott insulator state for $R3m$ structure by DMFT calculation under single-band Hubbard model picture when interaction parameter U is larger than 0.40 eV vs. band width of 0.25 eV. It is reasonable to assume that while lowering the temperature, $Fbar{4}3m$ structure GaTa$_4$Se$_8$ becomes $R3m$ structure GaTa$_4$Se$_8$ first, then $Pbar{4}2_{1}m$ structure GaTa$_4$Se$_8$, because of the symmetry of $Pbar{4}2_{1}m$ is lower than $R3m$ after Jahn-Teller distortion. The structure transition may explain the magnetic susceptibility anomalous at low temperature.