Os ancestrais da tribo Colville, cujos nomes não foram registrados, eram nômades, seguindo fontes de alimento conforme as estações mudavam. Esses nativos americanos, que viviam principalmente no leste de Washington, consistiam em vários bandos ou tribos que passavam o verão e o inverno em aldeias ou acampamentos. Oficiais do governo dos Estados Unidos deram o nome Colville aos índios americanos que negociavam em Fort Colville, Washington, independentemente de as pessoas serem realmente da mesma tribo. Hoje, muitos membros da tribo Colville vivem na Reserva Indígena Colville, que é administrada pelas Tribos Confederadas da Reserva Colville.
Como muitas outras tribos nativas americanas, a tribo Colville foi afetada pelos europeus antes que esses índios americanos tivessem contato físico com os estrangeiros. Isso veio na forma de cavalos, que foram importados da Europa no século 15 por exploradores europeus. Quando os cavalos alcançaram esses índios de Washington em meados de 1700, os cavalos permitiram que os nativos americanos viajassem em um território maior.
Durante os anos 1800, europeus, europeus canadenses e europeus americanos começaram a estabelecer entrepostos comerciais no leste de Washington para negociar mercadorias com os nativos americanos na área. O primeiro posto foi estabelecido ao longo do rio Columbia em 1807. Em 1825, a Hudson Bay Company fundou o Fort Colville, em homenagem ao lorde Andrew Colville da Inglaterra. O forte ficava em Kettle Falls, um local de comércio tradicional para as tribos de Washington.
À medida que os anos 1800 avançavam, mais pessoas de ascendência europeia mudaram-se para os terrenos tradicionais das bandas de nativos americanos que viviam na área. Como o comércio continuou e a demanda e competição por peles de animais como lontra, castor, urso e vison aumentaram, os comerciantes começaram a se referir aos nativos americanos na área como Colville por conveniência.
Muitos nativos americanos foram forçados a assinar tratados na década de 1850, confinando seu povo a reservas. O presidente dos Estados Unidos, Ulysses S. Grant (1822-1885), que foi um general chave para a União durante a Guerra Civil, estabeleceu a Reserva Indígena Colville por ordem executiva em 9 de abril de 1872. Uma ordem executiva é uma lei ou regra emitida pelo Presidente dos Estados Unidos que não requer aprovação do Congresso. A reserva original incluía não apenas pessoas que eram da “tribo Colville”, mas outros nativos americanos, incluindo alguns dos Coeur d’Alene, que significa “povo do furador” em francês, e os Methow, que tradicionalmente viviam ao longo do Methow Rio no norte de Washington. Demorou apenas três meses para que o governo dos Estados Unidos começasse a reduzir as terras desta reserva.
Hoje, muitos membros da tribo Colville e outros nativos americanos da área vivem em uma área que tem menos da metade do tamanho da reserva original. A Reserva Indígena Colville consiste em cerca de 2,300 milhas quadradas (5957 km quadrados). A tribo Colville e outras tribos nativas americanas na reserva produzem produtos de madeira e operam uma incubadora de peixes que fornece peixes para lagos e riachos no centro-norte de Washington.