Rotu on kehitetty Serra da Estrelan vuoristossa, nykyisen Portugalin alueella. Estrela-vuoristokoira on yksi Portugalin vanhimmista roduista. Estrelan esivanhempien varhaisimmat esi-isät olivat laumanvartijakoiria Serra da Estrelan vuoristossa. Niiden historiasta ei ole kirjallisia merkintöjä.
Elämä muuttui vain vähän alueen ihmisten ja koirien elämässä, jopa 1900-luvulle asti. Alueen eristyneisyyden vuoksi rotu oli suhteellisen tuntematon sen ulkopuolella aina 1900-luvun alkuun asti, ja silloinkin ne jäivät enimmäkseen huomiotta varhaisissa koiranäyttelyissä. Portugalilaiset ihailivat ulkomaisia rotuja paljon enemmän kuin omia rotujaan. Paimenkoirat kastroivat usein koiransa estääkseen niitä lähtemästä laumastaan parittelemaan. Näillä tekijöillä oli kielteinen vaikutus Estrelaan. Niinpä vuosina 1908-1919 järjestettiin concursoiksi kutsuttuja erikoisnäyttelyitä Estrela-rodun edistämiseksi ja säilyttämiseksi alueella. Tänä aikana yritettiin jonkin verran perustaa rekisteriä (josta ei ole säilynyt tietoja). Näyttelyihin kuului myös erityisiä karjanhoitajien työkokeita. Koe koostui siitä, että omistaja/paimen toi koiransa suurelle pellolle, jossa oli useita lammaslaumoja. Tuomarit tarkkailivat koiran reaktioita, kun se tuli pellolle ja kun lammaspaimen sai käskyn siirtää laumaa, mikä väistämättä tuotti harhailijoita. Koiran odotettiin siirtyvän vartiointipaikaltaan hakemaan harhailijat takaisin ja sen jälkeen ottavan johtavan aseman lauman kärjessä.
Ensimmäinen, alustava, kirjattu rotumääritelmä julkaistiin vuonna 1922. Tämä standardi kuvasi vain niitä toiminnallisia ominaisuuksia, joita luonnostaan löytyi tuon ajan parhailta koirilta, vaikka siinä mainittiin kastekynnet ”täydellistä” koiraa kuvastavina ominaisuuksina. Tyypillistä koukkumaista häntää ja taaksepäin kääntyneitä (rosoisia) korvia, joista myöhemmin tuli osa virallista standardia, ei mainittu tässä alustavassa standardissa.
Ensimmäinen virallinen rotumääritelmä kirjoitettiin vuonna 1933. Tässä standardissa Estrela pyrittiin erottamaan omaksi rodukseensa. Tämä johti siihen, että koukkuinen häntä ja kaksinkertaiset kyntökynnet tulivat vaatimukseksi. Kaikki värit olivat sallittuja. Standardiin on sittemmin tehty pieniä tarkennuksia. Koska he olivat enimmäkseen lukutaidottomia, he eivät pyrkineet noudattamaan virallista rotumääritelmää, jos edes tiesivät sen olemassaolosta. Mutta 1950-luvun alussa kiinnostus rotua kohtaan palasi, ja vuosittaiset concursot otettiin uudelleen käyttöön. Tarkoituksena oli jälleen herättää kiinnostusta Serran asukkaiden keskuudessa ja kannustaa heitä noudattamaan virallista standardia. Tänä aikana pitkäkarvainen rotu oli suosituin näyttelyissä, mutta ”näyttelykoirat” edustivat (ja edustavat edelleen) vain pientä osaa Portugalin Estrela-kannasta. Monet työkoirista olivat (ja ovat) lyhytkarvaisia.
1970-luvun alussa kiinnostus oli jyrkästi laskussa. Rodun rappeutumisesta ja jopa mahdollisesta sukupuuttoon kuolemisesta oltiin huolissaan. Portugalin vallankumous vuonna 1974 auttoi kuitenkin pelastamaan Estrelan. Se johti muutoksiin sekä Portugalin koiranäyttelyissä että portugalilaisissa koiraroduissa. Ennen vallankumousta koiranäyttelyt olivat olleet suurelta osin varakkaiden harrastus, ja he suosivat muita kuin portugalilaisia rotuja statussymboleina. Nyt työväestö saattoi esitellä ja esitteli suosimiaan kotimaisia koiria. Vallankumouksen myötä myös rikollisuus lisääntyi ja siten kiinnostus vahtikoiria kohtaan kasvoi.
Estrelasta ei ole tietoja Portugalin ulkopuolella ennen vuotta 1972. Vaikka joitakin niistä epäilemättä lähti maasta, ne todennäköisesti risteytettiin keskenään, eikä rotua pyritty säilyttämään. Vuosina 1972 ja 1973 tuotiin pareja Yhdysvaltoihin. Sittemmin Yhdysvaltoihin on luultavasti tuotu muitakin, mutta ensimmäinen paperoitu koira tuotiin Yhdysvaltoihin vasta vuonna 1998. Yhdistynyt kuningaskunta oli ensimmäinen maa, joka perusti rodun Portugalin ulkopuolelle vuonna 1972. Nykyään Estrela löytyy monista maista.
Tänä päivänä Estrela-vuoristokoira pysyy uskollisena vartijaperinnölleen. Se on edelleen työkoira, joka vartioi laumoja kotimaassaan Portugalissa ja muualla (Portugalin merijalkaväki oli käyttänyt niitä jopa partiokoirina). Se on myös ihanteellinen perheen lemmikki valppautensa, uskollisuutensa, älykkyytensä ja vaistonsa kasvattaa nuoria; kaikki ominaisuudet, joita se tarvitsi alkuaikoina.