After the addition of the Gadsden Purchase to the Arizona/New Mexico Territory, complaints began to arise about the inability of the territorial government in Santa Fe to effectively govern the area as a whole. On August 29, 1856, a convention formed in Tucson, sent a letter to the U.S. Congress, requesting the organization of the Arizona territory as a separate entity from New Mexico. The convention also requested that a delegate from the proposed Arizona territory be sent to Washington D.C. to represent the region's interests. Two hundred and sixty people signed the memorial that was sent to Washington, and Nathan P. Cooke was elected as the delegate for the territory. Sylvester Mowry later succeeded him. The proposal was brought before the House of Representatives in January of 1857. The bill was defeated, and the territory was not organized, because Congress deemed that the area had too small of a population to suffice as a full-fledged territory. However, a judiciary district was set up south of the Gila River, which Congress believed would be sufficient for the time being.

In 1857 Senator Gwin introduced a bill to organize the Gadsden Purchase area into the Arizona Territory. By February of 1858, the New Mexican Legislature passed resolutions in favor of the measure, but recommended some changes. First, the recommendation was made that the border between the Arizona and New Mexico territories be switched from an east/west line to a north/south line along the 109th meridian. Secondly, all the New Mexican Indians would be removed to Northern Arizona. Nothing came of this proposal, though Arizona persisted in their efforts. The politics of Washington D.C. hindered the development of the territory. The New Mexico/Arizona Territory was under the influence of Southern leadership and there was a fear that the entire plan was a scheme of Southern aggrandizement.

A Constitutional Convention was held in Tucson from April 2 to April 5, 1860 with thirty-one delegates. The convention established a provisional constitution "until Congress shall organize a territorial government and no longer. (1)" The area that the convention determined to be the "Arizona Territory" consisted of everything in the existing Arizona/New Mexico Territory below 30 degrees 40'. The territory was divided into four separate counties. Dr. L. S. Owings was elected to govern this new territory.