Según se cuenta en el libro Historia de los Varona, este pueblo fue fundado por Martín de Varona, para que se poblase de gente y acabar con tanta fiera que habitaba en esos montes. De hecho, el nombre lo tomó de la madre del fundador, Paula de Cárcamo.

Es digna de reseñar su ermita de San Juan, románica, con una curiosa inscripción que dice el año 1150, el Císter vino.

La iglesia de la Asunción fue fundada por Lope García de Salazar.