Antas und andere Funde belegen eine vorgeschichtliche Besiedlung. Aus römischer Zeit stammt u. a. der Ofen Forno da Pipa und ein Wegstein einer Römerstraße. Der Ortsname Arruda ist mit der hier zahlreich vorkommenden Rautenart (lat. Ruta) der Weinraute verbunden und entwickelte sich aus dem LateinischenRuta und Arabischenal-Ruta über Ar-Ruta zur heutigen Form.[4]
Der heutige Ort entstand vermutlich im Zuge der Wiederbesiedlungspolitik während der Reconquista. Erstmals offiziell erwähnt wurde Arruda in seiner Stadtrechtsurkunde, die Portugals erster König, D.Afonso Henriques im Jahr 1160 ausstellte. 1172 übergab er das Gebiet dem Santiagoorden, der die hiesige Landwirtschaft und insbesondere den Weinbau förderte. Der Ortsname Arruda erhielt daher im Laufe der Zeit den Zusatz dos Vinhos (port. für: der Weine).
König D.Manuel I. erneuerte die Stadtrechte 1517 im Zuge seiner Verwaltungsreformen. Er hielt sich zudem selbst eine Zeit in Arruda auf, als in Lissabon die Pest grassierte. Zum Dank ließ er hier die Kirche Igreja da Nossa Senhora da Salvação errichten (dt.: Kirche Unserer Lieben Frau der Errettung).
Arruda dos Vinhos ist Sitz eines gleichnamigen Kreises (Concelho) im Distrikt Lissabon. Am 19. April 2021 hatte der Kreis 13.992 Einwohner auf einer Fläche von 78,0 km²[3].