The first post office in Lake Providence was established on December 26, 1835. The town was located northeast of the present one, but the original site has long since caved into the Mississippi River or was destroyed during the Civil War. The Carroll Conservative of November 30, 1878, gives us the location of the post office: "The post office is now located on Lake Street (next door to Phil's Saloon). Where it will be located next week we will not venture to predict."