Willis Presbyterian Church and Cemetery, also known as Grace Baptist Church, is a historic Presbyterian church and cemetery in Willis, Floyd County, Virginia. It was built in 1954, and is one of six "rock churches" founded by Bob Childress and built between 1919 and the early 1950s. The building consists of a one-story, gable-fronted rectangular form with a roughly square, Gothic Revival bell tower on the building's northeast corner. The building was erected on a poured concrete foundation, and has walls of light framing covered with a thick quartz and quartzite fieldstone exterior veneer. It was listed on the National Register of Historic Places in 2007.