Родился в небольшом венгерском городке у озера Балатон в семье кантора местной синагоги. В 1834 году его семья переехала в городок Дойчкройц (ныне Австрия). Семья жила очень бедно. Карой, как его звали на венгерский манер, в 12 лет не умел ни писать, ни читать, но начал учиться игре на скрипке и на протяжении трёх лет занимался в музыкальной школе в городе Шопрон.
В возрасте 14 лет Карой переселился в Вену, к своему старшему брату Иожефу, бывшему тогда студентом-медиком. В Вене он продолжал заниматься игрой на скрипке, но брат не верил, что из Голдмарка выйдет хороший скрипач, и настоял на том, чтобы мальчик поступил в техническое училище. Поступив в училище, Карой одновременно сдает экзамены в Венскую консерваторию. Однако, вскоре в Вене разразилась революция и Карой вынужден был прервать учебу так и не приступив к ней. Йожеф Голдмарк, бывший одним из вождей молодых революционеров, должен был бежать из Вены. Бывший студент консерватории Карой Гольдмарк отправляется назад в Шопрон, участвует в боях на стороне венгерских повстанцев. В октябре 1849 года молодой музыкант становится скрипачом в оркестре шопронской театральной труппы. Летом 1850 года Голдмарк получил приглашение приехать в Буду. Здесь он играл в оркестре, выступающем на уличных площадках и в театре Будайской крепости.
В 1858 году Голдмарк впервые выступил с исполнением музыкальных произведений собственного сочинения. В начале 1860-х годов он играл в составе струнного квартета, благодаря чему познакомился с Иоганнесом Брамсом, который затем стал его близким другом. Вместе с Брамсом Голдмарк совершил путешествие по Италии. Кроме Брамса, композитор был близко знаком и с семьёй Иоганна Штрауса (младшего), работал совместно с Густавом Малером, дирижировавшим премьерами трёх опер Голдмарка («Домик у кузницы» (1896), «Военнопленные» (1899) и в новой постановке «Царицы Савской» (1901)). Много лет Голдмарк служил скрипачом в Карловом театре Вены, где изучал также игру на фортепиано, однако как композитор остался самоучкой. В 1863 году он получил от министерства образования поощрительную стипендию по музыке.
Первый успех к Голдмарку как к композитору пришёл в 1865 году с увертюрой
