Fleishman began playing tennis at the age of 8. At the age of 18, he played one season (1998–99) of collegiate tennis at the University of California at Los Angeles (UCLA), at the No. 2 position. That year Fleishman helped UCLA to the No. 1 ranking in the country, and to the final of the National Collegiate Athletics Association championships. In the ITF junior world rankings, he reached No. 18 in singles in 1998. After one year of competing on the collegiate level, Fleishman opted to turn professional in 2000.