Stutterheim is situated at the foot of the Eastern slopes of the Kologha Mountains, a spur of the Amatola Range, in the area of the Eastern Cape formerly called British Kaffraria.

Xhosa groups moved into the area in the first millennium. Missionaries arrived in the area in the 1830s from the Berlin Missionary Society, who established the Bethel Mission Station in 1837. At about the same time a fort was built and named Dohne Post after Dr Dohne, the first German Missionary. On 23 March 1857 members of the 3rd regiment of the British German Legion, under the command of General von Stutterheim, settled, some with families on plots of ground around Dohne Post and its immediate vicinity. A village of temporary huts quickly developed, and it was then decided to call the place "Stutterheim", after the commanding officer, who commenced building a large mansion which was never finished owing to his return to Germany on urgent private business, after only eight months in this country. There were hopes of von Stutterheim returning later, but these did not materialise, and he died at Wiesbaden, Germany in 1872, aged 65 years.

While some of the missionaries were mere opportunists out for adventure and soon drifted off to India or other parts of South Africa, many of those who settled with their families became successful farmers and hence as asset to their new-found "home".

These first inhabitants were joined in 1858 and 1859 by 34 German families who arrived at intervals in six sailing ships, all of which berthed at East London Harbour. The names of these ships are reflected in the Stutterheim street names today, e.g. Wandrahm, La Rochelle, Caesar Godefroy, Peter Godefroy and Johann Caesar. As the farmers gradually toiled towards prosperity, English and Dutch settlers moved into the area and steady commercial development took place. A 20 000 acre commonage was marked out and on 20 May 1879 Stutterheim was proclaimed a Municipality.