Sokolov was born in Leningrad, now Saint Petersburg, to Jewish father Lipman Girshevich Sokolov and Russian mother Galina Nikolayevna Zelenetskaya. He began studying the piano at the age of five and entered the Leningrad Conservatory's special school for children at the age of seven to study with Leah Zelikhman. After graduating from the children's school, he continued studying at the Conservatory with Moisey Khalfin. At 12, he gave his first major recital in Moscow, in a concert of works by Bach, Beethoven, Schumann, Chopin, Mendelssohn, Rachmaninoff, Scriabin, Liszt, Debussy and Shostakovich at the Philharmonic Society. At age 16, he came to international attention when the jury at the 1966 International Tchaikovsky Piano Competition awarded him the gold medal. It seems this may have been a surprising result: "16-year old Grisha Sokolov, who finally became the winner of that competition, was not taken seriously by anyone at that time."