After this, he was a teacher for several years until he was ordained by the Bishop Bartholomæus Deichman in 1730 and began working as a priest in Christiania.

From 1740 to 1743 he worked as a priest in the town of Stege, Denmark, as well as the dean for the whole island of Møn.

When Paludan took over the bishop's seat in Christianssand, he was surprised at how many beggars and poor people there were in the diocese.

Together with the county administrator Fredrik Georg Adeler, he began to work for a more effective poverty relief, but this was not easy.

On his first visit, Paludan spoke to the most powerful and richest men in every parish about helping the poor.