A finales del siglo XVIII los colonos blancos empezaron a emigrar desde las trece colonias originales por los Montes Apalaches hacia el «Oeste». Alrededor del cambio de siglo, empezaron a desplazarse lentamente hacia las partes orientales del Territorio del Noroeste, que se había establecido en 1787, y hacia partes del Viejo Sudoeste, o Alabama, Misisipi y el oeste de Kentucky y Tennessee. Consideraban a los pueblos nativos que residían allí como un obstáculo que había que conquistar o empujar más hacia el oeste.
Estados Unidos negoció la Compra de Luisiana en 1803. Aunque los límites permanecieron indefinidos hasta el Tratado Adams-Onís de 1819, después de 1803 el río Misisipi dejó de ser la frontera occidental de la nación. Los exploradores de esta enorme porción americana del oeste trans-Mississippi revelaron que la parte oriental era fértil y habitable. La parte media occidental, considerada por algunos como el «Gran Desierto Americano», se consideraba inhabitable.
El presidente Thomas Jefferson y los que le siguieron imaginaron una «zona de colonización india» o frontera india permanente, en una hilera de norte a sur en la orilla oeste del Misisipi. Muchos defendían este enfoque del «problema indio». Creían que el traslado de los indios a esa zona resolvería definitivamente el conflicto entre los habitantes nativos originales y los euroamericanos que clamaban por «civilizar» el continente. Los blancos vivirían al este del río y los indios al oeste. Uno de los principales defensores de la zona india del Misisipi fue el misionero bautista Isaac McCoy, que creía que la región debía convertirse en un territorio formal, con gobierno y leyes, para todos los indios. El concepto de una zona india se consolidó durante la administración del presidente John Quincy Adams y posteriormente se desarrolló plenamente bajo la dirección del presidente Andrew Jackson. La región concebida como «el país indio» se especificó en 1825 como toda la tierra situada al oeste del Misisipi. Con el tiempo, el país indio o el Territorio Indio abarcaría los actuales estados de Oklahoma, Kansas, Nebraska y parte de Iowa.
En realidad, el proceso de traslado de los indios había comenzado mediante tratados poco después de 1800. Además, muchas tribus simplemente huyeron hacia el oeste a medida que la línea de asentamientos blancos avanzaba hacia el río Misisipi y luego lo cruzaba. Algunos de los cherokees, por ejemplo, habían comenzado a desplazarse hacia el oeste en la década de 1810, con grandes migraciones hacia el centro-oeste de Arkansas en 1817 en una región que habían cambiado por tierras en el sureste. Poco antes del tratado con los cherokees de 1817 se produjo la «compra de Lovely» en 1816, y un tratado con los osage de 1818 despejó teóricamente el noreste de Oklahoma y añadió la tierra al dominio público. En 1820, los choctaw acordaron aceptar tierras entre los ríos Arkansas y Canadá y el río Rojo, en la actual Oklahoma.
Mientras tanto, los blancos también cruzaron el Misisipi y empezaron a ocupar una amplia franja que iba de norte a sur a lo largo de su lado oeste. Pronto densamente poblado, Missouri se convirtió en un estado en 1821 y Arkansas en un territorio en 1819. En 1824 se trazó un límite occidental para Arkansas, que incluía la totalidad o parte de los condados de Craig, Mayes, Delaware, Adair, Cherokee, Sequoyah, Muskogee, Wagoner, Haskell, Le Flore, Latimer, Choctaw, Pushmataha y McCurtain del actual Oklahoma. También incorporó la cesión de Osage de 1816 de la Compra de Lovely, así como una enorme porción de tierra prometida a los choctaw en el tratado de 1820. Ya en 1816 los blancos habían comenzado a asentarse en esta franja de tierra, que en 1820 fue incorporada por el Territorio de Arkansas al condado de Crawford, al norte, y al de Miller, al sur, extendiéndose incluso hasta el actual noreste de Texas. En 1827 se creó el condado de Lovely a partir del condado de Crawford, abarcando casi todo el actual noreste de Oklahoma, y su sede se estableció en el juzgado de Lovely (Nicksville), que más tarde fue la ubicación de la misión de Dwight en el condado de Sequoyah.
Los cherokees del oeste se opusieron a estar rodeados de blancos y de condados organizados de Arkansas. Los choctaw también se opusieron al condado de Miller y a sus residentes blancos. En 1825 un nuevo tratado ajustó la frontera oriental choctaw, y el condado de Miller se redujo. Muchos blancos que se habían asentado en esa región se trasladaron ahora al este de la nueva línea. En 1828, el gobierno federal aprovechó la situación para elaborar otro tratado con los cherokees occidentales en el que acordaron trasladarse al oeste de la nueva línea. El condado de Lovely fue abolido, y la frontera entre Arkansas y el Territorio Indio, en realidad las naciones choctaw y cherokee, se volvió a trazar en 1828 generalmente a lo largo de la actual frontera entre Oklahoma y Arkansas.
Durante las décadas de 1820 y 1830, docenas de tribus del noreste, medio oeste y sureste fueron expulsadas por medio de un tratado y en virtud de la Ley de Traslado de Indios de 1830, que autorizaba al presidente a obligar a las tribus a ceder sus tierras al este del Misisipi. Las que lo hicieran debían situarse al oeste de los nuevos asentamientos blancos, es decir, al oeste del meridiano 95. Una Ley de Comercio de 1834 definió además «el país indio» como toda aquella parte de los Estados Unidos al oeste del Misisipi y que no estuviera dentro de los estados de Missouri, Luisiana o el territorio de Arkansas, o cualquier otro territorio organizado. Los blancos fueron cuidadosamente excluidos de la región, para la mayoría de los propósitos, y el comercio de ellos con los indios fue regulado. A efectos judiciales, la región del norte (la mayor parte de la actual Kansas) estaba unida a Misuri y la parte del sur (la mayor parte de la actual Oklahoma) al Territorio de Arkansas (después de 1836, estado de Arkansas). Al parecer, en 1835 Isaac McCoy utilizó por primera vez las palabras «Territorio Indio» en la prensa.
Los Creek, Seminole y Chickasaw también sucumbieron a la migración forzada. Todas estas tribus del sureste habitaron a partir de entonces la parte sur del «Territorio Indio». Del mismo modo, numerosas tribus del noreste y del Territorio del Noroeste, incluidos los Kickapoo, los Miami, los Delaware y los Shawnee, fueron trasladados a la parte norte, el actual Kansas. Por lo tanto, en 1840 el Territorio Indio había sido poblado, escasamente, por grupos nativos pero no era un territorio formal u organizado.
Sin embargo, debido a que su tierra fértil resultó ser deseable para los blancos, con la Ley de Kansas y Nebraska de 1854 el Congreso organizó formalmente esas partes del norte del Territorio Indio en territorios oficiales que luego se convirtieron en estados. (Kansas entró en la Unión en 1861 y Nebraska en 1867.) Una vez finalizada la Guerra Civil, los indios fueron trasladados más al sur, a la parte del Territorio Indio que es la actual Oklahoma. Las tribus de las llanuras, como los cheyennes, arapahos, comanches, kiowas y apaches, se concentraron en reservas en la mitad occidental del territorio. En 1889 residían aquí más de tres docenas de tribus.
Para entender el significado completo del término «Territorio Indio», hay que entender también el proceso por el que una región se convirtió en territorio. Según lo establecido por la ley de los Estados Unidos, a partir de la Ordenanza del Noroeste de 1787, cuando una parte específicamente definida del dominio federal no organizado estaba suficientemente poblada, sus residentes (ciudadanos de los Estados Unidos) podían solicitar al Congreso el estatus de territorio. Posteriormente, el Congreso aprobaba una ley orgánica, con una declaración de derechos para los residentes del territorio, y establecía un gobierno tripartito con poderes ejecutivos y judiciales designados. Los residentes elegían un poder legislativo. El gobierno federal tenía la máxima autoridad sobre los asuntos territoriales, y un representante territorial elegido se sentaba en el Congreso. El Congreso nunca aprobó una ley orgánica para el Territorio Indio, aunque se propusieron algunas medidas, y se redactó un proyecto de ley, con ese fin. La región nunca tuvo un gobierno formal y siguió sin organizarse. Por lo tanto, el lugar geográfico comúnmente llamado «Territorio Indio» no era un territorio.
A finales del siglo XIX, el gobierno federal comenzó a asumir un mayor control sobre los acontecimientos que ocurrían en el país indio. En marzo de 1889 una ley estableció un sistema judicial federal con sede en Muskogee, asumiendo la autoridad y jurisdicción judicial que había sido ejercida desde la Ley de Comercio de 1834 por el Distrito Occidental de Arkansas. La medida de 1889 especificó por primera vez los límites acotados del Territorio Indio, ahora oficialmente reducido a un área delimitada por Texas al sur, Arkansas y Missouri al este, Kansas al norte y el Territorio de Nuevo México al oeste.
Pronto esta área se redujo de nuevo cuando se creó el Territorio de Oklahoma a partir de una parte del mismo mediante la Ley Orgánica de mayo de 1890. Se nombró un gobernador y se estableció una asamblea territorial de dos cámaras y un sistema judicial. El Territorio de Oklahoma, un territorio de buena fe de los Estados Unidos, podría optar a la condición de estado si su población crecía lo suficiente y si sus dirigentes seguían el proceso prescrito por la ley federal. La Ley Orgánica del Territorio de Oklahoma definió aún más estrechamente el Territorio Indio, reduciéndolo a algo más de la mitad oriental del estado actual. En la Convención de Sequoyah de 1905, los líderes indios trataron de eludir el proceso territorial y conseguir la condición de estado independiente para el Territorio Indio. Sin embargo, con la unión en 1907 de las naciones indias y el Territorio de Oklahoma como Estado de Oklahoma, ya no era viable un territorio o estado separado dominado por los indios. Durante el siglo XX, los historiadores, genealogistas y el público en general utilizaron el término genérico «Territorio Indio» para representar a toda la región de Oklahoma durante el período de la preestadidad.