Foi criada com a denominação Penhalonga e Paços de Gaiolo aquando da reorganização administrativa de 2013,[3] resultando da agregação das antigas freguesias de Penha Longa e Paços de Gaiolo. A sua designação foi alterada para Penha Longa e Paços de Gaiolo pela Lei 20/2017, de 23 de maio.[4]