Prestige gives you access to Diplomacy tasks such as Writs, Embassies and Missions. Some quests require a high Prestige.
Prestige is earned in only the largest cities through interacting with the people there. The longer you parley in a city, the higher your Prestige there will become. However, do not expect to gain Prestige with every parley. Building up Prestige takes time and effort.