Reeves and his family farmed until 1875, when Isaac Parker was appointed federal judge for the Natives Territory. Parker appointed James F. Fagan as U.S. marshal, directing him to hire 200 deputy U.S. marshals. Fagan had heard about Reeves, who knew the Territory and could speak several Native languages. He recruited him as a deputy; Reeves was the first black deputy to serve west of the Mississippi River. Reeves was assigned as a deputy U.S. marshal for the Western District of Arkansas, which had responsibility also for the Native reservation Territory. He served there until 1893. That year he transferred to the Eastern District of Texas in Paris, Texas, for a short while. In 1897, he was transferred again, serving at the Muskogee Federal Court in the Native Territory.