We analyze coronal holes present on the Sun during the extended minimum between Cycles 23 and 24, study their evolution, examine the consequences for the solar wind speed near the Earth, and compare it with the previous minimum in 1996. We identify coronal holes and determine their size and location using a combination of EUV observations from SOHO/EIT and STEREO/EUVI and magnetograms. We find that the long period of low solar activity from 2006 to 2009 was characterized by weak polar magnetic fields and polar coronal holes smaller than observed during the previous minimum. We also find that large, low-latitude coronal holes were present on the Sun until 2008 and remained important sources of recurrent high-speed solar wind streams. By the end of 2008, these low-latitude coronal holes started to close down, and finally disappeared in 2009, while smaller, mid-latitude coronal holes formed in the remnants of Cycle 24 active regions shifting the sources of the solar wind at the Earth to higher latitudes.