Pāvilostas vēsture ar aizsākusies ar pilsētas ostas celtniecību Sakas upes grīvā.
Pirmā informācija par vietu, kur Pāvilosta pašlaik atrodas rodama Hercoga Jēkaba periodā (1642-1682), kad kuģi varēja iebraukt Sakas upē un Pāvilosta kalpoja kā osta Aizputei. Ostu lietoja, lai eksportētu koku, graudus un citus produktus uz citām ostām Baltijas un Ziemeļjūrā, bija pat cieša sadarbība ar dāņu tirgotājiem.
Pēc kara starp zviedriem un poļiem 1660. gadā, Sakas upe bija aizsprostota pēc zviedru pieprasījuma, lai nodrošinātu attīstības iespējas Rīgas ostai. Ziemas laikā akmeņi tika savesti uz upes ledu un pavasarī, kad ledus kusa, tie nogrima tā, lai sašaurinātu kuģošanas ceļu kuģiem.
1855. gadā, Krimas kara laikā, Krievu robežsargi uzbūvē savu kordonu šeit, lai aizsargātu šo stratēģiski svarīgo vietu.
1878. gada ziemā Vācu lielskungs Otto fon Lilienfeld, kuram piederēja īpašumi tuvākajā apkārtnē pasūtīja pirmo mola konstrukciju, kas bija veidota no koka. Viņš par molu samaksāja 8000 zelta rubļus un pavasarī, kad palu ūdeņi padziļināja upes gultni, pirmās buru laivas varēja iebraukt ostā.
1879. gada 16. maija svētkos tika ielikts Kapteiņmājas pamatakmens. Šī ēka tika uzcelta tajā pašā gadā. Viņas vēstures laikā tā tika izmantota kā garu mājvieta, krogs, Vācu armijas kazarmas un muita. Pēc otrā pasaules kara tā bija administratīvā māja un noliktava vietējam zvejnieku kolektīvam „Dzintarjūra”. Vēlāk šajā ēkā tika atvērts Pāvilostas muzejs, kur varēja un joprojām var iegūt informāciju par Pāvilostas vēsturi un Sakas apkārtni.
Pilsēta, kura nemaz neeksistēja, tika nosaukta par Pāvilostu, Otto fon Lilienfeld brāļa Paula vārdā. Vēlāk osta tika arī dēvēta par „Pavlovskaja Gavan” ,arī „Pavlovsk”
Barons Lilienfelds nopirka 5 mazus kuģus un velkoni, kuri transportēja produkciju no viņa īpašumiem un Liepājas tirgu, nopelnot ar to lielu naudu.
1893. gada augustā, Krievijas Cars Aleksandrs III pasūtīja konstrukcijas Liepājas kara ostas celtniecībai. Bet šim darbam bija nepieciešams liels daudzums akmeņu. Un šie akmeņi tika ņemti no Pāvilostas apkārtnes un pa jūru transportēti uz kara ostu.
Laikā no 1890. līdz 1895. gadam, ostas mols tika pagarināts līdz 90 metriem. Kad akmens transportēšana beidzās, galvenās ostas darbības bija kuģubūve, zvejošana un tirdzniecība. Kuģošanas aktivitāte bija diezgan liela. Pirms Pirmā pasaules kara Pāvilostā bija apmēram 20 kuģošanas kārtība esoši kuģi un kabotāžas kuģi un arīdzan 100 zvejas laivas. Ostai bija pat savs glābšanas centrs. Lai nodrošinātu nepieciešamo dziļumu ostā, 70 000m³ smilts tika izsmelta ārā no jūras gultnes. Kā pierādījums par Jūras akmeņiem, 100m no krasta Pāvilostā atrodas Latvijas lielākais jūrakmens (P=15m , h=3,5m, zem ūdens 1,5 m).
No 1923. līdz 1929. gadam osta tika rekonstruēta un finansēta no valsts budžeta, tika paplašināts mols un padziļināta grīva. Valsts investēja 2,4 miljonus latu rekonstrukcijas darbos. Lai gan komerciālo aktivitāšu līmenis nebija augsts, galvenokārt koka eksports, ostai bija sava robeža, robežsardze un glābšanas vienība. Pāvilosta bija vislabāk uzturētā osta starp mazajām ostām Latvijā.
Vietējiem zvejniekiem piederēja 18 motorlaivas un 6 airēšanas laivas ar burām. Viņi ķēra placi, mencas, sardīnes un lašus. Ostai bija arī zivju apstrādes iespējas tīrīšanai, sālīšanai, kūpināšanai, kā arī saldējamās iekārtas.
Otrā pasaules kara laikā ostā netika veiktas nekādas komerciālās darbības, to lietoja tikai krasta apsardzes kuģi. Daudzi bēgļi aizceļoja uz Eiropu un Ameriku no šīs ostas. Kara laikā gandrīz visi vietējie kuģi un laivas tika iznīcinātas.
1949.gadā tika uzbūvēta jauna kuģu piestātne un degvielas noliktava, osta tika regulāri padziļināta.
Padomju laikā ostu vadīja zvejniecības kolhozs un vietējiem zvejniekiem bija ierobežota piekļuve ostai.
Līdz ar jahtu piestātnes Pāvilosta Marina izbūvi un atklāšanu 2006.gada 20.maijā osta ir ieguvusi ‘jaunu elpu’ un ir aizsācies jauns un nozīmīgs posms ostas attīstībā.