Now heading the household, Jane took her siblings back to Wyoming, arriving at Fort Bridger on May 1, 1868. Taking whatever job that was available in order to provide for the family, she worked as a cook, a nurse, a dance-hall girl, a dishwasher, a waitress, an ox-team driver, and according to some tales, a prostitute.

In 1870, she joined General George Armstrong Custer as a scout at Fort Russell, Wyoming, donning the uniform of a soldier. This was the beginning of Calamity Jane's habit of dressing like a man. Heading south, the campaign traveled to Arizona in their zest to put Indians on reservations. In her own words, Calamity would later say of this time, that she was the most reckless and daring rider and one of the best shots in the West.

In 1872, she returned to Fort Sanders, Wyoming, where she was ordered out to the Muscle Shell Indian outbreak. That campaign, in which Generals Custer, Miles, Terry and Crook were engaged, lasted until the fall of 1873. It was during this time that "Calamity Jane" reportedly earned her name.

As Calamity told the story, it happened at Goose Creek, Wyoming, where the town of Sheridan is now located. Captain Egan was in command of the Post and the troops were ordered out to quell an Indian uprising.  After a couple of days, when the soldiers were heading back to camp, they were ambushed by a large group of Indians. Captain Egan was the first to be shot and fell from his horse. Calamity Jane was riding in advance, but upon hearing gunfire, she turned in her saddle and saw the Captain fall. Galloping back, she lifted him onto her horse and got him safely back to the Fort. Captain Egan on recovering, laughingly said, "I name you Calamity Jane, the heroine of the plains.''

Afterward, she was ordered to Fort Custer, where she arrived in the spring of 1874. In the fall of that same year, they were ordered to Fort Russell where she remained until the spring of 1875. The troops were then ordered to the Black Hills to protect the settlers and the miners from the Sioux Indians where they remained until they arrived at Fort Laramie for the winter.

In spring of 1876, she was ordered north with General Crook to join Generals Miles, Terry and Custer at the Big Horn River. During this march, she swam the Platte river near Fort Fetterman to deliver dispatches from General Crook to a local outpost.  Contracting a severe illness, she was sent back in General Crook's ambulance to Fort Fetterman where she was hospitalized for fourteen days.