In July 1867, Kansas Governor Samuel Johnson Crawford issued a proclamation calling for volunteers to protect Kansans from Indian attacks in the west. The 18th Kansas Cavalry was brought up for four months as a result. Payne enlisted and was mustered in as the captain of Company D. This battalion replaced the Seventh Cavalry which had been transferred to the Platte River for the summer. In October 1868, Payne mustered in as a lieutenant in Company H of the 19th Kansas Cavalry, which served in a winter campaign against Indians on the western Great Plains. During this campaign, Payne served as a scout for General Philip Sheridan.