Worcester married Ann Orr of Bedford, New Hampshire, whom he had met at Andover. They moved to Brainerd Mission, where he was assigned as a missionary to the Cherokee in August 1825. The goals ABCFM set for them were, "...make the whole tribe English in their language, civilized in their habits and Christian in their religion." Other missionaries working among the Cherokee had already learned that they first needed to learn the Cherokee language. While living at Brainerd, the Worcesters had their first child, a daughter. Two years later, they moved to New Echota, established in 1825 as the capital of the nation on the headwaters of Oostanaula River in what is now Georgia. Worcester worked with Elias Boudinot (Cherokee) to establish the "Cherokee Phoenix" newspaper, the first published by a Native American nation. It was published in Cherokee, using the syllabary developed by Sequoyah, and in English.