Etymonline.com says:
Meaning "prostitute's client" is first attested 1915; earlier it was U.S. slang for "a robbery" (1865).
The Oxford English Dictionary has two relevant definitions, with first citations of 1926 and 1925:
10.
a. An instance of the sexual act or any of its variations; usu. spec. a prostitute's session with a client. Esp. to turn a trick, to perform a sexual act with a casual partner, usu. for money. slang (orig. and chiefly U.S.).
b. A casual sexual partner; usu. spec. a prostitute's client. slang (orig. and chiefly U.S.).
I found a citation slightly earlier than 1915.
A 1913 report (plain text) called The social evil in Syracuse: being the report of an investigation of the moral condition of the city by the Syracuse Moral Survey Committee interviewed prostitutes. Page 69 says:
September 11. Girl X201 was talked to at the State Fair Grounds
and at the X180 hotel. She was born in New York City 26 years ago
and has practiced prostitution for seven years. From this practice she
has received as high as $150 per week. She has one child. She has
been living with a man six years and said, "Well a good pal is worth
a whole lot. I have had a hard life. "When he has money I have it —
when I have it, it is his. We are good partners and I love him. He
makes good money, and I can turn good tricks myself. She is rough
and thoroughly degenerate.
One meaning of turn is to perform a service, as defined in this 1833 French and English Dictionary:
TURN [trick, an office good or bad] ... A friendly turn... An ill turn... Good turn... To do one a good turn... I'll do you as good a turn another turn... One good turn deserves another.
But again it links back to the earlier 1865 slang meaning of perform a robbery, do a job and around 1900-1915 it was also used for pulling off any (perhaps sordid or slightly underhand) feat, such as taking advantage in a baseball game (1900),performing sabotage (1906) "“turned a trick” in freezing out the minority holders of stock" (1902), or a politician says he won't "turn tricks for headlines" (headline and intro, 1912). It therefore seems natural that this would have also been used by prostitutes at the time, and appears to have stuck.