The band was named after the English revolutionary army of Oliver Cromwell. Led by guitarist / vocalist, Justin Sullivan (who performed briefly under the name 'Slade The Leveller' in the early 1980s), the group has an extremely loyal, global, multi–generational cult following called The Family. The band has also collaborated with electric violinist Ed Alleyne–Johnson, who worked with them on their Top 40 single "Vagabonds", and their albums Thunder & Consolation (1989) and Impurity (1990), as well as touring extensively with them for five years. New Model Army frequently tour with more than five band members.

The group also tours as 'Justin Sullivan and Friends', which means a more acoustic set without some players (which ones varies), and is linked to Red Sky Coven, in which Justin Sullivan also plays. In early 2003, Sullivan released Navigating By The Stars, a solo album recorded with other band members and featuring Michael Dean on drums, Dean White on guitar and keyboards, Danny Thompson on double bass, and Mark Feltham on harmonica. After a short tour at the end of 2004, the group returned to the studio to record their ninth studio album, Carnival (2005). EMI has released four remastered earlier albums. As the band themselves say: "Although there is nothing new within the packages they have been very sympathetically re–packed and remastered and do sound very, very good."[citation needed] The next studio album, High, was released in the UK on 20 August 2007, and in North America on 4 September 2007. On 5 September 2007, their North American tour in support of High was canceled when they were denied visas by the United States Citizenship and Immigration Services.

In 2004 their one–time drummer and founding member, Robert Heaton, died of pancreatic cancer.

One of their other members, Ricky Warwick went on to form The Almighty.