A brothel lets you build spies. Upgrading that to an inn will let you build assassins. After building a few assassins in one large city, I got an offer to establish an assassin's guild there for 1000 florins. Now in addition to the random 1-3 subterfuge all assassins begin with, each one has a +1 subterfuge due to training. I've got one good assassin so far; I had to start on captains. I couldn't kill off anything else. He's up to an 8 subterfuge now, and still going.

However, it doesn't look like you can transfer retinues around in this game, which will destroy one of my old tactics, that being to take my really good assassin and transfer his catamite/dancer/monkey over to a newly created assassin once the good one starts getting old.