Kozjanski Park was established in 1981 as Trebče Memorial Park (Law on Trebče Memorial Park, The Official Gazette of the Republic of Slovenia No.1/81). The area included the central and the eastern part of Kozjansko  region (along the Sotla river) and Bizeljsko hills on the southern part of Orlica. The main reason for establishing Kozjanski  Park originates from the historical heritage of this area. Marija Javeršek, mother of former Yugoslavian president Josip Broz - Tito, was born in Podsreda. Josip Broz spent a part of his childhood in Podsreda, and later, before and during the world war, he spent a lot of time with his aunt in Trebče.

The area gradually became known as Kozjanski Park for professional, system and promotional reasons. In 1999, the official name Kozjanski Park was given to the area with the Law on Natural Protection (The Official Gazette No. 56/99).