Goldin was of Polish Jewish descent and was born Hyman Elias Goldstein in Vilnius, which was then part of Russia but is now the capital of Lithuania. Sources differ as to his date of birth, some give it as 17 December 1873 and some as an unspecified date in 1874. An accident when he was young left him with a speech impediment. It has been said he showed a talent for magic tricks when he was young after he began learning from a gypsy performer. When he was 16 his family emigrated to the United States and settled in Nashville, Tennessee, where they ran a store. Despite the combination of a strong accent and a speech impediment, young Goldstein managed to make a living as a salesman.