The explosive magnetic energy release is widely accepted to have a crucial role in the flaring activity observed from ultra-strongly magnetized neutron stars, so called "Magnetars". We investigate, by means of relativistic magnetohydodynamic simulation, the nonlinear dynamics of the magnetized outflow triggered by the magnetic explosion on the magnetar surface. It is found from our study that the strong shock propagates in the interstellar medium in association with the expanding outflow. Its terminal velocity $v_{\rm term}$ depends on the strength of the dipole magnetic field anchored to the neutron star surface $B_{\rm dipole}$ and is given by a simple scaling relation, $v_{\rm term} \propto B_{\rm dipole}^{1/2}$. In addition, the outflow-driven shock can be accelerated drastically to the relativistic velocity when the density profile of the interstellar medium is steeper than the critical one, that is $ q \equiv {\rm d} \ln \rho(r)/{\rm d}\ln r \lesssim q_{\rm crit} = -5.0$, where $\rho (r) = r^{q}$ is the density distribution with index $q$ and $r$ is the distance from the stellar rotation axis. These results show that the relativistic outflow would be driven by the flaring activity on the magnetar surface in the realistic astrophysical condtion.