Carl Reinecke nasceu em Altona, Hamburgo, Alemanha; até 1864 a cidade esteve sob domínio dinamarquês. Estudou com seu pai, Johann Peter Rudolph Reinecke, professor de música. Carl começou a compor aos sete anos de idade, e sua primeira aparição pública como pianista foi aos doze anos. Aos 19 anos realizou a sua primeira digressão em 1843, pela Dinamarca e Suécia. Depois de uma estadia em Leipzig, onde estudou com Felix Mendelssohn, Robert Schumann e Franz Liszt, Reinecke saiu em turnê com Königslöw e Wilhelm Joseph von Wasielewski (mais tarde biógrafo de Schumann), no norte da Alemanha e na Dinamarca. Em 1846, Reinecke foi nomeado pianista da corte de Christian VIII em Copenhague. Lá permaneceu até 1848, quando renunciou e foi para Paris.