Leena Lehtolainen debuterade redan som 12-åring med ungdomsboken Ja äkkiä onkin toukokuu (’Och plötsligt är det maj’, 1976). Efter ytterligare en ungdomsbok samt några litteraturvetenskapliga verk om bland annat kriminallitteratur introducerade hon polisen Maria Kallio i sin första deckare, Ensimmäinen murhani (’Mitt första mord’, 1993).