Krall began to play the piano when she was four years old. She began to play in restaurants when she was 15. When she was 17, she won a Vancouver Jazz Festival scholarship (student money award) to study music at the Berklee College of Music in Boston. She later moved to Los Angeles to study with Jimmy Rowles. In 1990, she moved to New York City.