Bethlehem Primitive Baptist Church began in 1868 when 27 African Americans withdrew from nearby White Oak Church and chose the Rev. York Johnson, a former slave, as their pastor. Johnson founded the Union Branch of the True Vine, a mutual aid society, reportedly with the assistance of the Freedmen's Bureau. The church established a cemetery that enabled African Americans to exercise newfound autonomy over burial practices and funerals. Buried there are veterans of World Wars I and II and Korea. The church's sanctuary, built in 1870, was replaced in 1951. The Stafford County branch of the NAACP was founded there, and community members met there to plan strategies for the desegregation of local public schools.