Disclaimer: Don't blame me for your failures. Everyone has bad games and if you want to truly excel at a particular champion, you must practice and challenge yourself. As of this guide, I am a top 25 player: in the most recent Elo listing, number 15. In the previous, number 12. I am not claiming infallibility; simply that what is being said here has been tested, confirmed, and effective for the purposes of high tier play. Your experience will vary depending on the tier, opponents, and team-mates you play with.

I. Pre-Game:

A basic note out about the effectiveness of Katarina in any game is to make note of what other champions on your team have been chosen. For optimal efficiency, there should be at least two stuns and slows that your team-mates can use to help you pin down enemies either in ganks or team fights. Without a decent amount of disable, Katarina is not nearly as potent. While having a team without much disable capability is unusual, it happens, and is not pleasant. Make a concerted effort to balance out the team if you're able to, even if it means choosing another champion.

Masteries: 

There are two main builds that I've used. One focuses on supplementing offense, the other on defense. Generally, you want to stay away from any mastery lines that base their augmentation around mana.. because of course, Katarina has none. For this reason, most of the Utility tree is fairly worthless. 

Defensive Mastery Build: 

You get 60 bonus health with Veteran's Scars (Ardor is mostly filler towards Tenacity). Other benefits are small bonuses to armor/magic resist, and dodge (which will also boost speed with the extra focus talent). This helps survival early on particularly well. Early survival helps snowball to late game. The rest is spent in offense for the typical options - most importantly, Archaic Knowledge.

Offensive Mastery Build: 

Most important abilities in the Offensive tree are: Archaic Knowledge, Improved Rally, and Havoc. All of these improve your magic damage in a fairly significant way when coupled together. You will notice late in a game with these focuses active. In addition, Heal gets slightly improved in Defense, and we go again up to Dodge with a little MR. Some may ask: Why not get Brute Force? Well, I'll tell you why simply: both Sunder and Alacrity will outperform Brute Force over the course of a game, specifically once you've attained more than about 100 attack power.

Rune Build: 

Marks: There are two paths you can take with this - either straight Greater Mark of Malice (Tier 3 Crit Rune) or Greater Mark of Insight (Tier 3 Magic Penetration Rune). Physical Attack runes are simply not that good in comparison to these modifiers that effect percentages, rather than flat values as Attack runes do. I mainly utilize a full magic penetration page now.

Seals: Greater Seal of Evasion (Tier 3 Dodge Rune). These will help induce the Defensive Mastery Tree focus called "Nimbleness" that increases your speed by 10% any time you dodge. You'll hover around 9% in a game with talent + runes assuming no other modifiers. These are also important for survival early in the game when harassing an opponent with Shunpo, or dealing with aggressive ranged champions.

Glyphs: Greater Glyph of Celerity is a staple for many builds, and is no different here. Cooldown reduction is great to have, as the item build simply allows very little room for the addition of such items for Katarina.

Greater Glyph of Insight (Magic Pen) - I am now in the process of thoroughly testing magic penetration builds to assess their effectiveness. At the moment, it is at least as efficient as Celerity, when you factor in early game effectiveness. For a specific reason, cooldown reduction on Kat isn't as important: and that's because of her innate special ability that reduces cooldowns by 20 on kills or assists.

Quintessence: Greater Quintessence of Fortitude (Tier 3 HP Rune). This is pretty much a given in high tier play. Like all health items and runes, these were recently nerfed, but not hard enough to justify taking out of builds. Because of my aggressive playstyle, early game is very important to me, and these allow a little more leeway in that regard.

Summoner Spells:

With Defensive Mastery: Two choices here. Ignite + Cleanse, or Heal + Cleanse. It depends on your mentality. For the more aggressive user, go Ignite. If you feel that you need to fall back on Heal, then take that, as it's already included in the build. You can also switch these in and out depending on your team setup as far as summoner spells is concerned. Due to Cleanse's recent nerf, Ignite or Heal + Exhaust may also be a viable option.

With Offensive Mastery: Several choices are available. Heal + Rally is very viable. Essentially, though, any combination of Heal, Ignite, Rally and Cleanse will give you relative safety. Experiment and find what suits you best. 

My personal affinity is either towards Ignite + Rally or Heal + Rally. My style of play is fairly aggressive. Cleanse has gone totally out of favor (for me) due to the removal of the magic immunity on cast.

II. In-Game Setup:

Skill Build: 
1. Shunpo
2. Bouncing Blade
3. Killer Instincts
4. Shunpo
5. Bouncing Blade
6. Death Lotus
7. Shunpo
8. Bouncing Blade
9. Shunpo
10. Bouncing Blade
11. Death Lotus
12. Shunpo
13. Bouncing Blade
14. KI
15. KI
16. Death Lotus
17. KI
18. KI

Item Build Progression: 

Spawn: Doran's Shield, 1x Health Potion


1st Tier: Boots, Heart of Gold


2nd Tier: Heart of Gold -OR- Phage -OR- Aegis -OR- Giant's Belt (to start on Warmog's)

You may sell Doran's Shield at this point if necessary.

3rd Tier: B. F. Sword x2

You may sell Heart of Gold at this point if necessary.

End Game and Upgrades: Boots to Mercury Treads -OR- Sorcerer's -OR- Ninja Tabi

==== B. F. Sword

Upgrade: 2x B. F. Sword to Bloodthirster

==== Void Staff

Upgrade: 1x B. F. Sword to Infinity Edge or Bloodthirster

End Game Build (rarely ever happens, but this is what it would be): Boots of Choice, Warmog's/Frozen Mallet/Aegis, Bloodthirster x3 or BT x2 + 1 IE, and Void Staff.

Remember: Item builds are not to be adhered to 100% of the time. You should make use of your ability as a human to assess the way the game has gone so far and where it may be headed, and then use your best judgment to adjust your build as necessary.

III. Game Strategy 
Early Game:

I personally prefer to solo mid. However, if you are an inexperienced Katarina player, you should probably start honing your abilities in a lane with another player, preferably one with a stun. Your team-mate does not necessarily need to be ranged, as Katarina has some fairly hefty early harassing capability. The key to early game is being both elusive and aggressive at the same time, and yet being deceptively passive all the same. This would at first thought seem to be a conceptual impossibility, but when you are finally well-acclimated with Katarina's potential you will see this for its true glory.

So here is your bread and butter for harassment: Around level 3, start passively sweeping by in semi-wide arcs behind your creeps, slicing forward and back with the movement of enemy champions (as if in a dance). Always, always be moving back and forth, especially against skillshot champions (do not be idle). Hide behind your minions and use them as a wall, keeping distance from auto-attacks and spells. As you do this, activate Killer Instincts and the targetting for Bouncing Blade with Q (this champion is not for clickers - just a warning, you will probably not do well) and any time an enemy champion gets near enough, sweep forward and hit them with it, then immediately turn back and do as normal, making sure to last-hit any minions with either Shunpo or Auto-attack (hence, being passive-aggressive). Also, use side lane Brush to your advantage if able.

If you find that your team duo (or you solo) are harassing enough to keep the enemies on the defensive, start weaving a Shunpo in on enemy champions. The key here is to Shunpo, auto-attack ONCE, and then immediately turn tail and run. Use Bouncing Blade in unison when it's available. Now, this comes with a fair amount of risk if you're playing against champions with stuns and other disables. You must use good judgment. Death is rarely ever necessary. Champions with skillshots can be tricky. Again, a key concept here is deception: be unpredictable. If the last time you did this maneuver you went back one specific direction, then go a modified route next time. Never be predictable.

Now, on the converse, if you are being harassed, do not fret. Use Bouncing Blade and Shunpo to last-hit minions and simply concentrate on avoiding damage and staying in your lane. Also, as a general note, if you find that your harassment is largely ineffective due to healing, focus on farming and simply be ready for any opportunity that arises.

You may have the opportunity for a few kills early in the game. You have greater opportunity if you take Ignite as a summoner spell. You can also goad other champions into fights they can't win with Heal + Rally. 

At Level 6: With Death Lotus, you now have some prime killing/ganking potential. You will also have 1 rank of Killer Instincts. Most champions, except for tanks, will be killable when they go below half health. So, keep the harassment up on them - if they stay, if they decide not to err towards caution - make them pay for it. Bouncing Blade -> Killer Instincts -> Shunpo -> Pin yourself just slightly behind them, as long as you aren't in enemy tower range, and begin to Death Lotus. If you have Ignite, you can use this in the middle of channeling Death Lotus (it does not break channeling, same as other Summoner spells) for some nasty damage at level 6.

About Killer Instincts: One level is all you really need until it's the last thing to rank up. Use KI with Bouncing Blade to debuff healers. Otherwise, use KI + Shunpo when initiating against physical carries, or when running from them.

Around this time - you should have farmed enough for at least Boots and Heart of Gold. If you have not, work more on your last-hitting. Get these items when there is a lull in combat. The next set of items (Giant's Belt, Another HoG, Phage, or Aegis [this item is for situations in which your tank doesn't intend to get one, or if you have no tank]) are also possible in addition if you've had an especially terrific early game.

Mid Game:

This phase of the game is still mostly about laning, but now ganking is going to play a larger role not only against you, but for you. Do as you have done for most of early game: harass, farm, kill when able. Your next goal is to get enough for one of the second tier items if you haven't yet. If you have time, you can also grab a Lizard Buff, which will help with chasing down champions and give you extra harassing damage.

If you have Heart/2nd Tier Items, you can consider tower-diving for some kills. You won't take too much damage so long as you make it quick.

Team Fight Strategy: Because ganking, and eventually team fighting is now becoming important, it's time to explain the mentality and considerations you must take before initiating combat with Katarina. 

As Katarina, you should be one of the very last to get into a team fight. If your team has enough health to withstand the first barrage of enemy abilities, let them soak the damage and stuns/disables, and then go in for the clean-up. Typically, you'll enter as you normally do to kill a champion: choose the squishiest target with the least health, and one that lacks an escape mechanic. As you rank up Death Lotus, focus more on getting in an area where your ult will hit the max amount of squishies. For now, though, at rank 1 Death Lotus will only hit one player, so make sure it counts. 

Assuming you survived your little suicide rumble; immediately search for the lowest target within immediate vicinity, and Shunpo/BB them as necessary. Continue doing this as long as you are able. If you're low on health, or cornered, remember - SHUNPO can be used on ANY friendly or enemy target. Use it both as initiater, and escape mechanism. If you're using Rally, pop it right before you ult.

Katarina is the type of champion that for the majority of the game, because she cannot really keep anyone off of her once initiated (Shunpo'd), you're either all in or all out. What I mean by this is, if you're going to initiate, make it good or don't do it at all. This bridges on general team fight strategy and mechanics, though, so you'll have to use and cultivate your own judgment in specific situations. 

By Level 11: You should have at least a couple kills under your belt and have one B. F. Sword, possibly two. If you find that your enemy team is composed mainly of magic damage and disables (somewhat common), then you can forgo the second B.F. temporarily to get Mercury Treads earlier. If there are significant physical carries, you want to get Ninja Tabi. If the game lacks any clear direction towards magical or physical damage, then you can forgo both and upgrade to Sorcerer's for the extra magic penetration.

If you purchased a Giant's Belt at this point to augment health in the Tier 2 range, then now is also a good time to start to upgrade to Warmog's. I wouldn't do this before your first B.F. Sword, though.

Late Game:

As I've already explained most of what there is to know about Kat, the rest of the game will be largely dependent on your team setup, coordination, organization, etc. Katarina is very team-dependent, and you will usually fail if you don't have a decent supporting cast. Never bite off more than you can chew, and never go in first.

Continue farming your items, moving as a team when necessary, and being as badass with clutch kills as possible. Elixir of Fortitude is also a very good item to get if the team fights are even: it may be just enough to put you over the edge, as it provides health and attack for a cheap 300g. 

As a last note: In order to truly excel, work on your reflexes and timing. You must be able to identify, very quickly, the next target on your hit list in a team fight. Never stop, never slow down, and never let the other team recover. Be as elusive as possible, and make sure you use Shunpo just as often to escape as you do to attack. In the end, it is your job to finish what gets started.