We propose a model in which intermediate-mass black holes (IMBHs) with mass of ~10000 Msun are formed in early dark matter halos. We carry out detailed stellar evolution calculations for accreting primordial stars including annihilation energy of dark matter particles. We follow the stellar core evolution consistently up to gravitational collapse. We show that very massive stars, as massive as 10000 Msun, can be formed in an early dark matter halo. Such stars are extremely bright with Log L/Lsun > 8.2. They gravitationally collapse to form IMBHs. These black holes could have seeded the formation of early super-massive blackholes.