We developed a new direct-tree hybrid N-body algorithm for fully self-consistent N-body simulations of star clusters in their parent galaxies. In such simulations, star clusters need high accuracy, while galaxies need a fast scheme because of the large number of the particles required to model it. In our new algorithm, the internal motion of the star cluster is calculated accurately using the direct Hermite scheme with individual timesteps and all other motions are calculated using the tree code with second-order leapfrog integrator. The direct and tree schemes are combined using an extension of the mixed variable symplectic (MVS) scheme. Thus, the Hamiltonian corresponding to everything other than the internal motion of the star cluster is integrated with the leapfrog, which is symplectic. Using this algorithm, we performed fully self-consistent N-body simulations of star clusters in their parent galaxy. The internal and orbital evolutions of the star cluster agreed well with those obtained using the direct scheme. We also performed fully self-consistent N-body simulation for large-N models ($N=2times 10^6$). In this case, the calculation speed was seven times faster than what would be if the direct scheme was used.