Horst Köhler, Polonya'nın Skierbieszów şehrinde doğdu. 8 çocuklu çiftçi bir ailenin 7. çocuğudur. Babası Eduard Köhler ve annesi Elisabeth Köhler uzun süre Alman göçmenlerin 1856 yılında kurduğu Romanya'nın güneyinde, ve Moldavya'nın 30 km kuzeyinde bulunan Bessarabien şehrinin Ryschkanowka köyünde yaşadılar. Aynı bölgede 1940 yılından beri 400 Alman asıllı göçmen yaşıyordu. 1940 yılında Adolf Hitler'in işgali sırasında adı Heidenheim olarak değiştirilen bölge, Sovyet Ordusu'nun müdahalesiyle düştü. 1942 yılında Köhler ailesi Lublin'e taşındı. Orada 1943 yılında Horst Köhler doğdu.
Gençliği
1944 yılında Horst 1 yaşına geldiğinde annesi Warthegau'da arka arkaya 3 çocuk daha yaptı. Horst Köhler'in babasının arkadaşları askere alınmasına rağmen, o köyde çiftçi olarak kaldı. 1945 yılında Kızıl Ordu sınırı geçerek onların bulunduğu bögleyi tehdit edince, diğer milyonlarca Alman gibi Köhler ailesi de batıya doğru kaçmaya başladı. Kaçışları Sachsen Anhalt eyaletinde bulunan Leipzig kentinin Markkleeberg kasabasında noktalandı. Köhler ailesi burada çitçilik hayatını yeniden kurdu. 1953 yılında sosyalistler çiftçiliği ve ziraati tehdit etmeye başlayınca Köhler ailesi Doğu Almanya'yı (DDR) terketmek zorunda kaldı. Kacış yeri bu sefer Batı Almanya'nın Berlin kentiydi. 1957 yılına kadar Köhler ailesi Baden Württemberg eyaletinin Stuttgart kentinde bulunan Backnang kasabasındaki bir iltica sığınma kampında yaşadılar. Bir ilticacı çocuğu olarak Horst Köhler liseyi burada bitirdi.Son olarak aile Ludwigsburg'a taşınarak orada kalmaya karar verdi. 1963 yılında Horst Köhler burada temel öğrenimini tamamladı. Horst Köhler çocukluğunda izciydi. Dini ve politik görüşleri konusunda objektif bir düşünce tarzı vardı. İnsanların milliyetlerinden ve dinlerinden dolayı eleştirilmesine karşıydı. Herkes onu Daniel lakabı ile çağırıyordu. Kendisi ile yapılan bir röportajda kendisini hiç bir ilticacı olarak görmediğini ve burayı vatan kabul ettiğini söylemişti.