Експедицијата на Коронадо од 1540 година низ централно Мексико и во современиот американски југозапад забележала дека имало Керехос, генерално признаено дека се предци на источните апачи, на Лано Естакадо, огромна рамнинска област во источно Ново Мексико, западен Тексас и југозападна Оклахома . Querechos беа опишани како високи и интелигентни; тие живееле во шатори, се вели дека се како оние на Арапите, и ги следеле стадата бизони, од кои обезбедувале храна, гориво, алатки, облека и капаци за типи - сето тоа се транспортирало со помош на кучиња и травоа. Овие Керехо тргувале со земјоделски пуеблоски народи. Почетниот контакт бил мирен, но до средината на XVII век дошло до сеопфатна војна меѓу Шпанците и Апачите. Во текот на седумнаесеттиот век, шпанската власт на југозапад се спроведувала со често невозможни барања од Пуеблос, кои, пак, се нашле подложени на апахиските напади кога шпанската експлоатација не оставила ништо за трговија. Во исто време, сите домородни луѓе беа десеткувани од болести за кои немаа имунитет. Имаше и притисок од Уте и Команче кои се движеа кон југ во областа која претходно ја држеше Апачи. Документираните докази сугерираат дека Шпанците го вооружувале Команче за да им помогнат во нивните неуспешни напори да ги покорат и контролираат апачите.

Мескалеро брзо зеде коњиод Шпанците, што им го олеснува ловот, трговијата и рациите бескрајно. Тие, исто така, ја позајмиле шпанската практика на тргување со робови и на тој начин им дале оружје на Шпанците да го користат против нив со тоа што шпанските колонисти, додека земале робови од заробениците Апачи, поттикнале страв кај Пуеблос дека тие ќе бидат следните робови што Апачите ги барале. Всушност, Апачите почнаа помалку да се потпираат на трговијата со Пуеблос и повеќе на рациите против шпанските колонисти.

И покрај шпанската политика на спротивставување на племињата, вторите се здружија во 1680 година во бунтот Пуебло и успешно ги отстранија Шпанците од Ново Мексико. Многу луѓе од Пуеблоа, кои побегнале од Шпанците отишле да живеат со Апачи и Навахо, се вратиле дома и се чини дека постариот модел на лов на Рамнините и тргување со Пуебло бил повторно воспоставен. Во 1692 година колонистите се вратија и темпото на војна со Апачи се забрза.

Историјата на осумнаесеттиот и почетокот на деветнаесеттиот век е напишана во крв и неисполнети ветувања. Предавството беше неконтролирано и мировните договори не вредеа колку мастило беше потребно за да се напишат. Мескалеро рутински биле нарекувани „непријател, незнабошци, апаши“ и биле обвинувани за практично секоја катастрофа што ги снашла шпанските колонисти. Вистинскиот ефект на Шпанија беше минимален и Мексико сè уште не беше независна земја. Северната граница на Нова Шпанија им била доверена на неколку војници набогатство, несоодветно снабдена и обучена војска, платеници трговци, љубоморни групи католички мисионери и смели цивили кои се обидуваат да одземат живот од земја што не простува. Во средината на ова, шпанските регенти инсистираа да ги третираат Апачите како обединета група на луѓе кога тие беа многу бендови, секој под номинална контрола на раководител; Договорот потпишан со таков поглавар никого не обврзуваше на мир, и покрај спротивните желби на Шпанија.

Во 1821 година, Мексико стана независно од Шпанија и го наследи проблемот со Апачи-барем неколку децении. Ропството, од страна на сите страни, и должничкиот пеонаж го достигна својот зенит во овој период. До 1846 година, генералот Стивен Вотс Керни ја презеде контролата врз најсеверните делови на мексиканската граница и основаше седиште во Форт Марси во Санта Фе, Ново Мексико. Договорот од Гвадалупе Идалго во 1848 година формално отстапи големи делови од она што сега е американски југозападен дел на Соединетите Држави и повеќе беше додадено во 1853 година со купувањето на Гадсден, пренесувајќи го „проблемот Апачи“ во Соединетите држави. Договорот од 1848 година им гарантираше на колонистите заштита од Индијанците, Мескалеро; не се споменуваше индиските права. Конгресот, во 1867 година, го укина пеонажата во Ново Мексико, а заедничката резолуција (65) од 1868 година конечно стави крај на ропството и ропството. Меѓутоа, проблемот со Апачи остана.

Мескалеро бешесобрани (често) и држени (ретко) во Боске Редондо во Форт Самнер, Ново Мексико, од 1865 година, иако армиските агенти задолжени за нив постојано се жалеа дека доаѓаат и си оделе со алармантна фреквенција. Четири века речиси постојан конфликт и десеткување од болести, заедно со губењето на копнената база што ги одржуваше сите заедно за да го сведат Мескалеро на тажни неколку до моментот кога нивната резервација беше воспоставена.

Доцните 1870-ти до тинејџерските години на дваесеттиот век беше особено тешко време, поради несоодветната храна, засолниште и облека. И покрај сопственото страдање, тие ги прифатија своите „роднини“, прво Липан, а подоцна и Чирикахуа, на својата резервација. До 1920-тите имаше мало, но значително подобрување во животниот стандард, иако обидите да се направат фармери од Мескалеро никогаш не успеаја. Индискиот акт за реорганизација од 1934 година откри дека Мескалеро е желен и целосно способен да ја преземе контролата врз сопствените животи, борба што и денес ја водат низ судовите за прашања за користење на земјиштето, правата на водата, правната јурисдикција и чување. Иако арената на борбата за опстанок се пресели од коњи во племенски авион кој често патува во Вашингтон, Апачи се уште се страшни непријатели.