We have studied the formation of coronal holes (CHs) associated with halo CMEs. For this study, we used multi-wavelength data from Yohkoh Soft X-ray Telescope (SXT), GOES Soft X-ray Imager (SXI), SOHO EIT 195 ${AA}$, SOHO MDI magnetogram, MLSO He I 10830 ${AA}$, and BBSO H-alpha. The CHs are characterized by open magentic field regions with low emission, density, and temperature and their open fields drive high speed solar winds which cause geomagnetic storms. So far, the formation and the evolution of CHs are not well understood. The formation of the dark region associated with the eruption of a CME is well known as "coronal dimming" which may be caused by the mass depletion near the CME footpoint. It is different from a typical CH since it persists for only one or two days. In this study, we present three cases that show the formation of coronal holes which are associated with three halo CMEs: 1) 2000 Jul 14, 2) 2003 Oct 28, 3) 2005 May 13. In the first case, hot plasma was ejected during a weak eruption and then filled out the pre-existing CH. After the halo CME occurred, the hot plasma region becomes a CH again. In the second and the third cases, we found newly formed CHs just after their associated CMEs. All three coronal holes are associated with strong flares and persist over 3 days until they disappeared by the solar rotation. Examining the MDI magnetograms, we found that the magnetic polarity of each CH region has one polarity. Based on these results, we suggest that the coronal holes can be formed by the CMEs and they should be distinguished from the coronal dimming.