Bouldin was born probably in Charlotte County, the son of Wood Bouldin and Joanna Tyler Bouldin. His father was a prominent local attorney, and his mother was a sister of Governor John Tyler, making him a cousin of President John Tyler. Bouldin read law, possibly in his father’s office, and was admitted to the bar on December 6, 1802, by which time he was presumably about twenty-one years old. He married Ann Bickerton Lewis in Richmond on December 19, 1804. They had six sons and five daughters before she died on December 25, 1823. On March 7, 1825, Bouldin married Eliza Watkins Spencer, of Charlotte County. They had four sons.