We report a measurement of the electric dipole moment of the $tau$ lepton ($d_tau$) using an 833 fb$^{-1}$ data sample collected near the $Upsilon(4S)$ resonance, with the Belle detector at the KEKB asymmetric-energy $e^+ e^-$ collider. Using an optimal observable method, we obtain the real and imaginary parts of $d_tau$ as ${rm Re}(d_tau) = ( -0.62 pm 0.63 ) times 10^{-17} ~e{rm cm}$ and ${rm Im}(d_tau) = ( -0.40 pm 0.32 ) times 10^{-17} ~e{rm cm}$, respectively. These results are consistent with no electric dipole moment at the present level of experimental sensitivity and improve the sensitivity by about a factor of three.