By the 1870s most of the mail in the United States was transported by railroad or steamship. In isolated area of the South and West, though, the federal government offered lucrative contracts to private carriers who delivered the post via horse, stagecoach, or wagon. These federal contracts used asterisks ("stars") in place of the words "certainty, celerity, and security." Some contractors colluded to submit absurdly low bids, sometimes for non-existent routes, which Post Office officials accepted, then negotiated much higher payments from Congress and pocketed the profits. By 1880, there were nearly 10,000 star routes, costing the federal government nearly $6 million a year to maintain.

In 1880, Congress learned that some members of both parties were involved in the Post Office contract fraud. President-elect James Garfield was informed of the matter, and shortly after his inauguration in March 1881, the Republican president ordered his new postmaster general, Thomas James, to investigate. Evidence soon pointed to corruption, in Garfield’s words, "of a very gross and extensive kind." In April, the president forced the resignation of Thomas Brady, the second assistant postmaster general. In June, a clerk of Senator Stephen Dorsey of Arkansas, chairman of the Republican National Committee, admitted wrongdoing and incriminated Dorsey and members of the senator’s family. President Garfield insisted that investigators "Go ahead regardless of where and whom you hit," and encouraged prosecutors to move more swiftly.

After Garfield’s death by an assassin’s bullet in September 1881, President Chester Arthur removed more implicated Post Office officials, and vowed to carry the investigation through "with the utmost vigor of the law." On March 4, 1882, Brady, Dorsey, and seven other men were indicted by a grand jury for fraud. Various reasons, including stalling tactics by defense attorney Robert Ingersoll, delayed the trial until June. Nearly 150 witnesses were heard and 3,600 documents placed into evidence, but only Dorsey’s clerk and another minor defendant were found guilty.

When the jury foreman claimed an attempt had been made to bribe him, a retrial was set. In the meantime, President Arthur fired five federal officials who expressed sympathy with the defendants. The second trial ran from December 1882 until June 1883, with even more testimony and documents than the first one. This time, despite more evidence and a stronger charge to the jury from the judge, all the defendants were found not guilty. Local cases continued, but only resulted in the conviction of two minor defendants.