Der Ortsname deutet fälschlicherweise auf eine alemannische Siedlung hin. Er geht jedoch auf eine Namensübertragung des Dorfes Hirrlingen am oberen Neckar zurück. Die dort ehemals ansässigen Herren von Hurningen gründeten um 1100 auf den Höhen über dem unteren Lautertal eine neue Burg, die schließlich Herrlingen genannt wurde. Die Anlage wurde 1247 und 1378 zerstört und wieder aufgebaut. 1588 begann unter Dietrich von Bernhausen der Bau des heute noch erhaltenen Schlosses. Der im Blautal gelegene Burgweiler gleichen Namens taucht erst im 16. Jahrhundert in den Quellen auf. Wie in allen Burgorten im Blautal befanden sich auf der Albhochfläche die Felder, während die Talaue als Wiesenland genutzt wurde. Der Ort bestritt seinen Lebensunterhalt überwiegend aus der Landwirtschaft. Doch neben dem herrschaftlichen Domänenbetrieb konnten sich bäuerliche Anwesen nicht entwickeln. Allenfalls hatten die Untertanen kleine Hanf- und Krautländer zur Eigenbewirtschaftung.

Darüber hinaus waren sie zu unentgeltlichen, täglichen Diensten auf den herrschaftlichen Feldern verpflichtet. Erst im 18. Jahrhundert bekamen sie dafür eine bescheidene Verköstigung und geringen Lohn. Mit dem Ende des herrschaftlichen Staatswesen besserte sich die Lage, weil die Gemeinde Ackerland ankaufte. Neben der Landwirtschaft entstand ein bescheidenes Gewerbe. Eine Getreide-, eine Papier- sowie eine Ölmühle waren am Ort. Bereits im 16. Jahrhundert gab es eine Schmiede. Wagner, Gärtner, Schreiner, Hafner, Schuster, Maurermeister und Schneider arbeiteten ausschließlich für den örtlichen Bedarf. Die ersten nachweisbaren Herrschaftsträger waren die, aus dem oberen Neckarraum stammenden Herren von Hurningen, welche kurz nach 1100 im Blautal auftauchten. Der Machtwechsel zu den Herren von Bernhausen, ursprünglich aus dem Filderraum stammend, erfolgte gegen Ende des 15. Jahrhunderts. Bis zur Mediatisierung 1802 blieben die Bernhausen reichsunmittelbare Lehensleute.

Das unter bayerischer Herrschaft neu gebildete bernhausische Patromonialamt Herrlingen wurde dem bayerischen Landgericht Söflingen zugeordnet. Nach dem Übergang an Württemberg Im Jahr 1810 hob man diese Regelung wieder auf und gliederte den Ort in das Oberamt Blaubeuren ein. In der Folgezeit wurden die Lehensträger vom neu entstandenen Königreich Württemberg bestimmt. 1839 kamen das Schloss und die dazugehörigen Ländereien an die Mauclers, einer Hugenottenfamilie, deren Mitglieder zahlreiche württembergische Staatsämter bekleideten. Die Herrschaft über den Ort ging den Mauclers dabei jedoch verloren. Mit der Auflösung des Oberamts kam die Gemeinde 1938 schließlich an den Landkreis Ulm. Im Zuge der baden-württembergischen Kreisreform wurde der Ort in den Alb-Donau-Kreis eingegliedert und kam mit der folgenden Gemeindereform am 1. Januar 1975 nach Blaustein.

Herrlingen genoss bereits Mitte des 19. Jahrhunderts als Sommerfrischeort einen guten Ruf. So baute sich der Ulmer Glockengießer Philipp Jakob Wieland um 1860 ein Landhaus am Rande der Gemeinde. Die von seinem Sohn Max Robert 1904 in unmittelbarer Nachbarschaft erbaute Jugendstilvilla (Villa Lindenhof) war die bedeutendste in einer Reihe von Sommerresidenzen, wie sie in Herrlingen um 1900 errrichtet wurden.  Zwei Produktionsstandorte der Wieland-Werke wurden schon kurz nach 1900 ins bayerische Vöhringen verlegt. Die Kalksteinverarbeitung spielt nach wie vor eine wichtige Rolle. Schon lange ist der Ort wegen seiner ansprechenden Lage geschätzt.