Un premier cimetière est probablement implanté à cet endroit en même temps qu'est fondé le petit prieuré dépendant de l'abbaye de Villemagne, attesté en 1170. L'église attenante, citée sous le vocable de Saint-Etienne-de-Pezan, est la première église paroissiale de Puissalicon. Elle perd son statut dans le deuxième quart du 13e siècle au profit de l'église Notre-Dame, située sur les hauteurs du village près du site castral. L'église Saint-Etienne-de-Pezan et son prieuré sont mentionnés dans les archives communales aux 15e, 16e et 17e siècles : acte de donation d'un inconnu, effectuant des legs aux églises de Notre-Dame-de-Crau et de Saint-Étienne-de-Pézan, réalisé entre les mains des consuls de Puissalicon, fin 15e siècle (224 EDT 138) ; fragments de reconnaissances de certains habitants de Puissalicon pour des possessions relevant de la fabrique de Saint-Etienne-de-Pézan" : acte dressé par Raymond Jougla, début 16e siècle, (224 EDT 142). L'église, endommagée lors des guerres de religion, est réparée par la communauté en 1626 (224 EDT 140). La tour, qui s'élève encore dans l'enceinte du cimetière, est l'élément le mieux conservé de cet ensemble religieux. Au 19e siècle, une lithographie publiée dans les Voyages en Languedoc de Taylor et Nodier en donne à voir des vestiges plus nombreux qu'à l'heure actuelle.

Si la fondation du cimetière est parfois située postérieurement à la Révolution (BACOU, p.96), plusieurs indices archéologiques et textuels semblent au contraire aller dans le sens d'une fondation médiévale. En effet, un tombeau datant du 13e siècle - dont il ne subsiste aujourd'hui que le couronnement formé d'un arc brisé orné de tores, de filets et d'une rangée de fleurons - s'élève à proximité de la tour. De plus, dans le courant du 14e siècle, plusieurs membres de la famille Boussagues, dont dépend la seigneurie de Puissalicon, demandent à être inhumés dans le cimetière de Saint-Etienne-de-Pezan (citons notamment le testament de Pierre de Boussagues, daté de 1348, 224 EDT 133). Dans le compoix de la commune dressé en 1606, le cimetière de Saint-Etienne est le seul à être cité sur le territoire communal (224 EDT 204). Enfin, en 1748, l'évêque de Béziers en visite dans la paroisse de Puissalicon ordonne de faire "un cimetière près du village avec une croix au milieu, entouré de murailles, fermé à clef, où il y aura une place pour les enfants mort-nés sans baptême ; l’ancien, qui est fort éloigné et dont le chemin est impraticable interdit dans dix-huit mois ; une bière commune pour les pauvres" (1 MI 267/1). L'ordonnance ne sera pas suivie d'effet.

Le 23 janvier 1853, le conseil municipal établit un règlement concernant l'établissement de concessions dans le cimetière (224 EDT 224, non paginé). Le site s'étend alors sur 2131 mètres carrés (il en compte aujourd'hui 7400). Le cimetière est agrandi à plusieurs reprises, notamment dans le dernier quart du 19e siècle (224 EDT 345) et en 1963.