Reutlingendorf wird 790 erstmals urkundlich genannt. Das Kloster Sankt Gallen erhielt in jenem Jahr umfangreichen Besitz. Die Herren von Reutlingendorf, vermutlich Niederadlige, sind um 1200 bis 1431 genannt.
Im 15. Jahrhundert ist ein Großteil der Grundherrschaft als klösterliches Lehen nachweisbar. Der Lehenbesitz war in den Händen der Herren von Reutlingendorf, ein Teil der Güter wurde 1360 an die von Hornstein verkauft, die wenig später auch die Ortsherrschaft innehatten. Daneben waren auch die Herren von Stein begütert, die die von Hornstein teilweise beerbten und zusammen mit diesen 1419 das Dorf an das Kloster Obermarchtal verkauften. Das Kloster Sankt Gallen verzichtete 1420 auf seine Lehensrechte. Weiteren hornsteinischen Besitz erwarb das Kloster 1440.
In Reutlingendorf wurde bis in die 1950er Jahre der Brauch des Dorfwächters gepflegt, woran seit 2007 der von dem Bildhauer Josef Alexander Henselmann geschaffene Dorfwächter-Brunnen, am Ortseingang von Obermarchtal her kommend, erinnert.[1][2]
Zum 1. April 1972 wurde die ehemals selbständige Gemeinde Reutlingendorf in die Gemeinde Obermarchtal eingegliedert.
Gemeinde Obermarchtal, Ortsverwaltung Reutlingendorf (Hrsg.): 1200 Jahre Reutlingendorf: 790–1990. Zur Geschichte und mit Geschichten eines schwäbischen Dorfes zwischen Bussen und Donau. 1. Auflage. Süddeutsche Verlagsgesellschaft, Ulm 1991, ISBN 3-88294-162-6.
