The Regions Beyond Missionary Union originated in 1873 when the East London Training Institute for Home and Foreign Missions was opened by Henry Grattan Guinness (1835-1910) in Stepney Green, Clapton, London. Guinness, a nephew of Arthur Guinness the founder of the brewing empire, had already made his name as a revivalist preacher of some note attracting crowds of up to 10,000 at a time. Grattan Guinness had been strongly influenced by James Hudson Taylor, the founder of the China Inland Mission, whose appeal for trained missionaries for China was one of the factors which prompted Guinness, with his wife Fanny, to establish the college.

The first student, Joshua Chowriappah from India, enrolled at the beginning of 1873, by the end of that year the college had moved to bigger premises at Harley House in Bow, and later expansion included a property in Derbyshire (Cliff College 1875) and a separate college for women (Doric Lodge 1884). The college offered a mixture of theory with opportunity for practical work around the East End. Mission halls were opened for meetings and teaching, a nursing centre and medical mission were established, and the Institute purchased its own mission yacht the 'Evangelist'. No fees were charged, the Institute was to be run by faith alone, it accepted students from many different nationalities and was interdenominational. By 1915 1500 missionaries had been trained and sent around the world, some joining established missions and others forming their own societies.

In 1887 Guinness handed the administration over to his son (Harry Grattan Guinness 1861-1915) but remained closely involved, travelling widely to attract support for the Institute. The Guinness family connection was to last into the 1970s through the support of Henry Grattan Guinness's grandson, Gordon Meyer Guinness (1902-1980). The first decade of the twentieth century brought financial difficulties and disagreements about the type of training that was to be offered. Cliff College was sold, the number of students at Harley was cut and in 1915 the college closed completely. By this time, however, the work had expanded in different directions.

Regions Beyond magazine was published from 1878 describing the Institute and giving news of missionaries and missions around the world. In the same year the Guinnesses and a group of friends arranged for a number of missionaries to go to Congo as the Livingstone Inland Mission and the Institute took full responsibility for the project from 1880 until 1884. In 1888 the Guinnesses launched a new mission to Central Africa, the Congo Balolo Mission. To encourage support the Regions Beyond Helpers Union was formed in 1892 and membership reached 11,000 by 1897. Expansion continued: in 1897 the Institute took responsibility for the support of a group of Harley students working in Peru and later for others in Argentina and in 1899 the first missionaries were sent to the Bihar region of India. In the same year the name of the Institute was changed to the Regions Beyond Missionary Union and the RBMU was incorporated in 1903.

Throughout the twentieth century Regions Beyond (from 1981 Horizons) published news of the mission's work, conferences were organised, and pamphlets, books, lantern slides, photographs and films were produced to raise awareness and increase support. The financial difficulties of the early twentieth century affected all areas: the mission was able to continue to operate in Congo and India but the South American work was passed to the Evangelical Union of South America in 1911. The period after the Second World War was, however, a time of expansion with the absorption of the Peru Inland Mission (1948) and entry into Kalimantan (Borneo, 1948/9), Irian Jaya (1954) and Nepal (1954, with the United Mission to Nepal).

Despite, and in some ways because of, the mission's successes some began to question the role and purpose of the mission, especially in relation to the indigenous churches and other organisations. The wide diversity of fields stretched resources and administration and the idea of co-operating with other similar agencies was increasingly proposed. The North American councils (which had met as separate bodies since 1948) sometimes took a different view on these and other issues and in 1979 the London based RBMU UK split from its overseas councils, the latter operating as RBMU International. In the UK the mission became more involved in joint projects and in 1980 moved to office premises shared with other agencies. It still sought ways to maintain its own identity and considered expanding to new areas such as Pakistan, Thailand, and the Philippines. From the late 1980s, however, it became increasingly clear that it was no longer suitable for the mission to continue as it was. In 1990, after negotiations with other bodies, the work in each area was passed to new or existing agencies, although some missionaries remained with RBMU until 1991.