For those with Connecticut ancestors, you might be interested in the records of over 600 churches dating back to the 17th century that the Connecticut State Library holds. That's right, the records of over 600 churches.
The homepage for this collections explains, "The Church Records Index covers, at best, only about one-quarter of the church records held by the Connecticut State Library, mostly Congregational. For information on what church records were abstracted, check the Guide to Church Records in the Connecticut State Library (looking for entries that have been annotated "SLI"). There is no specific cutoff date for the index; most entries date before 1850, but there are some to the early 1900s."
Just another good example of how sometimes, you may not church records at a church.