Shortly thereafter, Neil Halstead (vocals and guitar), Rachel Goswell (vocals) and Ian McCutcheon (drums and percussion) started recording demos, which they sent to various record companies. 4AD founder Ivo Watts-Russel got hold of the demo and signed them.
The first record, "Ask Me Tomorrow", was released on November 1995, and a tour began with various acts. The record featured Christopher Andrews on Piano (He later became Rachel's husband and is now playing in the group Cuba), Simon Rowe on lead guitar and Audrey Riley on cello.
After having toured across UK, Europe and USA, with Simon Rowe and Poppy Gonzalez on piano (who was later replaced by Al Forrester), they began to record their second LP. The single "Who Do You Love" was released in June 1998, followed by "Some Kinda Angel" in September. The second album "Out Of Tune" was then released in October. The band then proceed with a live tour, with Bernard Butler among others (Neil played with his band simultaneously). The band also did some songs for the soundtrack of the movie "A Walk On The Moon" , but only one of them, a cover of Love´s "No Matter What You Do" was included on the actual CD.
In 1999 and beginning of 2000, Mojave 3 toured very little and recorded their 3rd album, "Excuses For Travellers", which came out in May 2000.
A 4th album, "Spoon And Rafter", was released on September 2003.