Lehtolainen was born in Vesanto, Northern Savonia. Her first novel was released when she was only 12 years old. She studied literature in Helsinki until 1995 and wrote crime novels from 1993 on. Since about 2007 she has written other genres of books. Her works have been translated into various languages: Spanish, Dutch, Chinese, Lithuanian, Polish, French, Swedish, German, Estonian, Czech. Leena Lehtolainen is married to Mikko Lensu and she has got two children (Konsta Johannes, born in 1991 and Otso Olavi born in 1994). She lives in Degerby, west of Helsinki.
Lehtolainen won the Finnish crime novel society yearly prize in 1997 and 1998. She received the Espoo city Award of Arts in 2000, and was nominated for the Glass Key award in 2003.