The name derives from the Anglo-Saxon Willesdune, meaning the "Hill of the Spring" and a settlement bearing this name dates back to 939 AD.

Willesden was bounded on the north-east by the Roman Watling Street, later Edgware Road, on the north and west by the river Brent, and on the south-east by the Kilburn brook. An ancient track, some of it forming part of Harrow Road and Kilburn Lane, marked most of the southern boundary. The soil is mostly heavy and poorly drained clay, probably once covered by thick oak forest and well-adapted to the grass farming that characterised the area from the 18th century.

From the 14th to 16th centuries, the town was a place of pilgrimage due to the presence of two ancient statues of the Virgin Mary at the Church of St Mary. One of these statues is thought to be a Black Madonna, which was insulted by the Lollards, taken to Thomas Cromwell’s house and burnt in 1538 on a large bonfire of "notable images" including those of Walsingham, Worcester and Ipswich. There was also a "holy well" which was thought to possess miraculous qualities, particularly for blindness and other eye disorders.

The river Brent, running from north-east to south-west, flooded frequently. It was dammed between 1835 and 1839 to form the Welsh Harp along the northern boundary, but although the reservoir and feeders to the canal reduced the Brent it remained capable of serious flooding. The principal tributary of the Brent in Willesden was the Mitchell brook which entered the Brent north of Stonebridge and was itself formed from two tributaries. The northern branch, called the Sherrick or Slade brook, rose near Edgware Road at Cricklewood and flowed through Sherrick green where it was joined by a stream flowing northwards from Willesden Green. The southern branch rose south of Willesden Green and flowed west and north through the open fields. South-east of the Brondesbury ridge the land drained into the Kilburn brook, also known as West Bourne, Ranelagh Sewer, or Bayswater rivulet.

The parish of Willesden remained predominantly rural up until 1875, when its population was 18,500. However, this changed with the opening of the Metropolitan Railway (later the Metropolitan line) station of Willesden Green on 24 November 1879. By 1906 the population had grown to 140,000, a phenomenon of rapid growth that was to be repeated in the 1920s in neighbouring areas such as Harrow. The Metropolitan line service was withdrawn in 1940, when the station was served by the Bakerloo line, and later the Jubilee line.

Willesden became an urban district in 1894 and a municipal borough in 1933. In 1965, it joined Wembley and Kingsbury in the London Borough of Brent.

World War I caused Willesden to change from a predominantly middle class suburb to a working class part of London. After the war, Willesden grew rapidly as many factories opened up with numerous flats and houses. The local council encouraged building to prevent large unemployment and decline. To the present day, Willesden has been shaped by the patterns of migration which marks it out as one of the most diverse areas in the United Kingdom. City of London Corporation records show that the first black person recorded in Brent was Sarah Eco, who was christened in St. Mary’s Church in Willesden on 15 September 1723. The 1901 United Kingdom census recorded that 42% of the population was born in London. In 1923, the specialist coach builder Freestone and Webb established their base in Willesden, producing bespoke cars on Rolls-Royce and Bentley chassis until 1956.