The way to do it right is to wash the holster first. Really scrub it. The product to use is marseille soap on a damp cloth. Repeat as many times as you need to get it really clean, ie. the (preferably white) cloth stays white. Let it dry for at least 2-3 days before you do anything else, you don't want any moisture trapped in leather. You can get a bar of this soap from almost anywhere and it's cheap, it's often used for hand washing wool garments.
When that's done we can get to conditioners. Any good quality commercial conditioner will do, even though marseille soap itself is already a (mild) conditioner. What Earlsbud said about butter is new to me and I'd be adventurous enough to try it.
Background: I've had a few collectible cars with leather seats and after trying all kinds of commercial leather care/cleaning products, washing the leather thoroughly with marseille soap has yielded better results than any of them by themselves. Even old, slightly dried leather looks and feels like new after you're done. So far I've only tried it on one leather holster, which turned out fantastic.