Vuonna 1942 Venäjän "Military Council" päätti, että armeijan tulisi käyttää koiria ja jokaiseen osastoon on otettava koiran kouluttajia, tämän tuloksena perustettiin koulu "School of Junior Dog Training Specialist". Koulussa oli sotilaallinen, urheilu ja laboratorio -osastot. Työkoiria koulutettiin vartiointiin ja miinan etsintään.

Toisen maailmansodan aikana (1939-1945) monet työkoirista kuolivat puolustaessaan maata ja valtion omistama kenneli "Central Military School of Working Dogs (CMSWD)", joka myös tunnettiin nimellä Red Star Kennel, laitettiin vastuuseen siitä, että se tuottaisi armeijalle työkoiria.

Koirat tuotiin pääasiassa valloitetuista maista kuten itä-Saksasta, kokonaisia koirajunia toi koiria Moskovassa sijaitsevaan Veshnyakin regioonaan, jossa CMSWD sijaitsi tuolloin. Red Star Kennel sai resurssit käyttöönsä, liikkeelle lähdettiin yli 100:sta koirasta eri roduista, kokeilut käynnistyivät samanaikaisesti. Laboratoriossa kokeiltiin rotuyhdistelmiä, yhteensä uskotaan käytettäneen 17 eri rotua, osa kokeiluista oli epäonnistuneita. Colliet, bokserit ja dopermannit osoittautuivat hyödyttömiksi armeijan käytössä. Saksanpaimenkoiran ja laikan yhdistelmät eivät myöskään toimineet. Tavoite yhdistää tanskandoggin koko ja voima saksanpaimenkoiran pidempään turkkiin epäonnistui. Mukana oli myös isovillakoira, jota yhdistettiin etelävenäjänpaimenkoiraan. Epäonnistuneet yhdistelmät poistettiin jalostuksesta. Yksi onnistunut kokeiluhaara oli moskovannoutaja (rotusekoitus newfoundlandereita , kaukasianpaimenkoiria ja itäeuroopanpaimenkoiria), jota käytettiin mustaterrierin jalostuksessa.

Suunnitelman pohjana oli suursnautserit, rottweilerit ja airendalinterriererit. Jalostussuuunnitelman tekivät yhteistyössä koiran käyttäytymiseen erikoistunut eläintieteilijä (kynologi) ja biologi, professorit N.A. Iljin ja G.P.Medved. Tavoitteena oli:

1. vaihe, suursnautserin ja airendalinterrierin risteytyksiä

2. vaihe, suursnautserin ja rottweilerin risteytyksiä

3. vaihe, suursnautserin ja moskovannoutajan (rotusekoitus newfounlandereita, kaukasianpaimenkoiraa ja itäeuroopanpaimenkoiraa) risteytyksiä

4. vaihe, risteyttää edellämainittujen yhdistelmien pentuja

Airendalinterrieri on älykäs, sillä on itseluottamusta, se on ystävällinen, rohkea ja peloton koira

Suursnautseri on suuri, dominoiva, älykäs, helppo kouluttaa, monikäyttöinen ja hyväluontoinen koira.

Rottweiler on suuri itsevarma koira. Alunperin se on jalostettu karjan ajamiseen, nykyisin sitä käytetään vartioimiseen.

Mustaterrierin jalostamiseen käytettiin mm. seuraavia koiria:

Suursnautseri urokset: Zorab (rek nro 7411D), Roy (rek nro U720P)

Airendalinterrieri narttuja: Sotta (rek nro 4U78C), Sima (rek nro 47U3C9, Sembi (rek nro 4942C), Salma (rek nro 48U6C)

Rottweiler narttuja: Uda (rek nro 59UOY), Una (rek nro 58UOY), Femka (rek nro 7OU5OP), Urma (rek nro 73UOY)

Jalostus alkoi massajalostuksella, mutta havaittiin, että suursnautseriuros Roy jätti tasaista jälkeä. Se astui rottweilereita, airendalinterriereitä, newfoundlandereita, etelävenäjänpaimenkoiria ja jätti aina jälkeensä suuria mustia pentuja, joilla oli karkea karva päässä ja jaloissa. Royta voidaan pitää rodun kantaisänä, ensimmäinen Royn pentue syntyi 1951.

Alussa oli monenlaisia ongelmia, kuten purentavirheitä, hammaspuutoksia, puuttuvia kiveksiä, valkoisia läiskiä jne, jotka eivät vastanneet tavoitteita. Kun ohjelmaa jatkettiin, kaikki virheelliset pennut poistettiin jalostuksesta. Vuonna 1955 Red Star Kennel esitti mustaterrierin Moskovassa tapahtumassa nimeltä: "All-Union Exhibition of Economy Achievements". Koirat otettiin hyvin vastaan ja työ sai kultamitalin ja diplomin erinomaisuudesta. Kokeilu jatkui ja vuonna 1957 Red Star Kennel alkoi tarjota toisen ja kolmannen sukupolven mustaterrieripentuja yksityisille ostajille ja kasvattajille, rotu levisi Balkanin maihin, Ukrainaan ja Siperiaan.

Vuonna 1958 julkistettiin mustaterrierin rotumääritelmä. Rotumääritelmä julkaistiin kirjassa "Manual for training and usage of Military Dogs". Yksityisillä kasvattajilla ja Red Star Kennelillä oli erimielisyyksiä rotumääritelmästä, Red Star Kennel oli tuottanut hyvin tasaisia koiria luonteeltaan, mutta koirien ulkonäkö vaihteli. Yksityiset kasvattajat halusivat säilyttää käyttöominaisuudet, mutta lisätä näyttävyyttä vaatimattoman näköiseen koiraan, kun taas Red Star Kennel halusi säilyttää lyhytturkkisen rodun, jossa trimmaus ei saisi näytellä liian suurta osaa, sillä koirat elivät kenneloloissa..

Vuonna 1970 tuotiin Suomeen ensimmäiset Neuvostoliiton ulkopuolelle tuodut koirat, narttu Jolka ja uros Max. Maxin tyttäret Anastasia ja Alicjezebal astutettiin isällään. Rotu levisi Unkariin, Tsekkoslovakiaan, USA:han ja sai tunnettavuutta. Vuodesta 1958 vuoteen 1979 jalostus ja kokeilut jatkuivat. Vuonna 1979 Red Star Kennel ja DOSAAF (Army Navy and Fleet Volunteer Support Organization) viimein pääsivät yksimielisyyteen rotumääritelmästä. Siihen mennessä yli 800 pentuetta oli kasvatettu tuloksena yli 4000 pentua, joista suurin osa täytti rotumääritelmän. 1980-luvun alussa mustaterrieriä näytettiin kansainvälisissä näyttelyissä ja vuonna 1981 rotu hyväksyttiin viralliseksi Venäjällä. FCI (The Federation Cynologique Internationale) hyväksyi rodun 29.9.1983, FCI:n uusi rotumääritelmä julkaistiin 19.2.1996 (tarkennukset koirien kokoon). Voimassa oleva rotumääritelmän suomennos on Suomen Kennelliiton hallituksen hyväksymä 12.1.1987.

Suomen Mustaterrierit ry perustettiin 25.2.1987, vuonna 2009 jäseniä oli 109. Suomessa arvioidaan olevan 350-400 mustaterrieriä, pentuja rekisteröidään 50 vuodessa. Kasvattajia oli vuonna 2009 7 kappaletta.