According to the United States Census Bureau, the city has a total area of 35.56 square miles (92.10 km2), of which 34.73 square miles (89.95 km2) is land and 0.83 square miles (2.15 km2) is water. The elevation is 1,063 ft (302 m) above sea level.

The city is bounded on the northern side by Interstate 94, the south by the plane of 60th Street South, the west by Century Avenue, and the east by Manning Avenue. The adjoining cities in these directions are, respectively, Oakdale, Landfall, Lake Elmo, Cottage Grove, Maplewood, Newport and Afton.

Woodbury is composed of upland between the valleys of the Mississippi River and St. Croix River. The northeast corner of Woodbury lies within the watershed of Valley Creek, one of the few remaining trout streams in the Twin Cities area. Valley Creek flows eastwards to the St. Croix River at Afton, Minnesota. The city also contains several small lakes, including Powers, Wilmes, Colby, Carver, and Battle Creek. Battle Creek lake is the source of Battle Creek, which flows westwards to the Mississippi River in Saint Paul.

At almost 36 square miles in size, Woodbury is a direct descendant of one of the congressional townships that Minnesota Territory was divided into when the territory was ceded by the Native Americans of the United States and "opened to settlement." Woodbury was originally named Red Rock, but was renamed Woodbury after Levi Woodbury, the first justice of the Supreme Court of the United States to attend law school, after it was realized that another Red Rock Township existed in Minnesota. When first settled in 1844, the land was mostly wood but was converted to farmland. The township government was organized in 1858. One of the city's few surviving 19th-century farms, the Charles Spangenberg Farmstead, is listed on the National Register of Historic Places.

In 1955, the first suburban development broke ground in Woodbury: Woodbury Heights. After some years of growth, the town government could not adequately provide services for new developments, and it became clear that Woodbury needed the government of a village with extra privileges. The earliest proposal for incorporation officially came in 1963 after two years of debate.

The Minnesota Municipal Commission had recently found that the fragmented way in which the Minneapolis suburbs and the suburbs around White Bear Lake had developed was disadvantageous, as it made coordinating sewers, public water systems, and other utilities difficult. Thus, the Commission had been encouraging towns to incorporate in full whenever possible.

Since 1961, the Town of Cottage Grove had been petitioning to become a village, and the Minnesota Municipal Commission took it upon themselves to push for a joint incorporation of Woodbury and Cottage Grove as the Village of Washington. The idea was agreed upon by the two town commissions, and the issue was put up for a vote during the general election of 1963. It lost with 662 votes for joint incorporation, and 1,284 against. Cottage Grove would later incorporate on its own in 1965.

In 1966, a series of meetings took place setting up the incorporation of the Village of Woodbury. A vote was conducted on February 14, 1967, with 543 voting for incorporation, and 164 against. The Village was officially incorporated on March 7, 1967.