Leonhard usually spends time near the thrones for the Lords of Cinder (in Firelink Shrine). He first appears after you light the Tower on the Wall bonfire in the High Wall, or after defeating Vordt. Speak with him to acquire 5 Cracked Red-Eye Orbs, which can be used to invade other players as a hostile Red Phantom.
Once you light the Cliff Underside bonfire in the Undead Settlement, or defeat the Curse Rotted Greatwood and you have a Pale Tongue in your inventory, Leonhard reappears in the shrine. Speak with him to acquire the Lift-Chamber Key. You can use this key to descend through a locked door in the High Wall of Lothric, beneath the Tower on the Wall bonfire. Deep in the chamber is a Darkwraith. Defeat it, and you can acquire a full Red Eye Orb, which can be used for unlimited invasions of other players. Defeating the Darkwraith also causes Leonhard to appear once more in the shrine.
Your next encounter with Leonhard only occurs if you join Rosaria’s Fingers in the Cathedral of the Deep and offer or use at least one Pale Tongue (though be aware that doing so antagonizes Sirris of the Sunless Realm if you are pursuing her questline). Leonhard appears at the exit to her chamber after you do so.
Still later, after you have joined Rosaria’s Fingers and you have reached the Profaned Capital bonfire or defeated Yhorm the Giant, Leonhard slays Rosaria. Return to her body to find the Black Eye Orb. Take the Orb to the highest room in Anor Londo, it will activate, allowing you to invade Leonhard and slay him to recover Rosaria’s Soul, as well as the Crescent Moon Sword and the Silver Mask. This also causes the Shrine Handmaid to sell Leonhard’s Armor set.