Mittfältaren tillbringade tre år på Tannadice men gav sig av efter att ha förvisats från premiärministern.
Saints manager Tommy Wright berättade sin klubb webbplats: "Paul är underskattad - han är en aggressiv spelare men har en hel del riktig kvalitet också.
"Hans passning är utmärkt och under hela den här karriären har hans attityd på planen varit stor."
St Johnstone har redan säkrat midfielders Blair Alston och Michael Coulson från Falkirk respektive York City, medan defeners Keith Watson gör bytet från St Mirren.
"Vi tror att vi har fångat en annan bra signering för den kommande säsongen - vår fjärde - och jag tror att i alla fyra vi ger kvalitet och erfarenhet i truppen," sade Wright.
"Det förbättrar inte bara kvaliteten utan också djupet vi sitter, tror jag, i en bra position.
"Jag har alltid betonat att det är hela gruppen som har gjort det möjligt för denna fotbollsklubb att uppnå vad den har de senaste säsongerna och tillägget av Paul kommer att förbättra det."
Paton gick med i United sommaren 2013 från Partick Thistle, som fortsätter att göra 90 framträdanden för klubben.
Han var kapten på sidan i de senare stadierna av förra säsongen och tackade klubbens supportrar "och alla på Tannadice" på klubbens hemsida.
"Det kommer alltid att finnas en tangerine plats i mitt hjärta och jag önskar Dundee United all framgång i att återvända till skotska Premiership nästa säsong," sade han.
Hitta alla de senaste fotbollsöverföringarna på vår dedikerade sida.
Paul Paton har undertecknat ett tvåårigt avtal med St Johnstone efter att ha lämnat Dundee United genom "ömsesidigt avtal".