Té una rica història, ja que el poblat que li dónadona origen data dels inicis de la colonització [[Espanya|espanyola]]. La seva denominació deriva del frare o ''fray'' (en [[guaraní]]: 'pay') [[Policarpo Sandú]], qui va fundar una [[reducció]] amb dotze famílies aborígens procedents de les [[Missions jesuítiques]] l'any [[1772]] pràcticament al lloc en el qual es va desenvolupar l'actual ciutat.<ref>[http://books.google.cat/books?id=NMtkAAAAMAAJ&q=canelones+Gr%C3%BCndung&dq=canelones+Gr%C3%BCndung&hl=ca&ei=SnFlTbp_gZDhBvi7haQG&sa=X&oi=book_result&ct=result&resnum=7&ved=0CEUQ6AEwBg "Süd- und Mittelamerika", S.233 de Wilhelm Sievers] {{de}}</ref><ref>[http://books.google.cat/books?id=t9qwTnsBvtAC&pg=PA439&dq=paysand%C3%BA+1772&hl=ca&ei=M3dlTd2ZL8Wp8QOPqry9Bw&sa=X&oi=book_result&ct=result&resnum=3&ved=0CDMQ6AEwAg#v=onepage&q&f=false "Central and South America", S.439 de A.H.Keane] {{en}}</ref>
Paysandú va ser [[Setge de Paysandú|assetjada]] pels [[Portugal|portuguesos]] i [[brasil]]ers en tres oportunitats i és famosa per l'heroica defensa que van fer els seus habitants el [[1865]], sota el comandament del General [[Leandro Gómez]], en fer front al setge de les tropes del General [[Venancio Flores]] i dels seus aliats brasilers.<ref name="uruguay"/>
