Kolehmainen is a Finnish surname. Notable people with the surname include:
- David Kolehmainen (1885–1918), Finnish wrestler
- Eero Kolehmainen (1918–2013), former Finnish cross country skier
- Hannes Kolehmainen (1889–1966), Finnish four-time Olympic Gold medalist and a world record holder in middle- and long-distance running.
- Janne Kolehmainen (born 1986), Finnish ice hockey player
- Kristiina Kolehmainen (1956–2012), Finnish-Swedish librarian
- Mikko Kolehmainen (born 1964), retired Finnish flatwater canoer
- Olli Kolehmainen (born 1967), Finnish canoer
- Seppo Kolehmainen (1933–2009), Finnish film actor
- Tatu Kolehmainen (1885–1967), Finnish long-distance runner
- Toni Kolehmainen (born 1988), Finnish professional football midfielder
- William Kolehmainen (1887–1967), Finnish-American long-distance runner