Ahri

Her charm and stupidly high mobility makes your ult close to useless in lane. Pre-six, try to avoid her orb of deception and her charm as much as possible while also harassing her with your abilities. If she uses her charm, don't be afraid to get up close and try to land a Q followed by your combo on her. This way once she hits six, she can't engage on you because she'll be too low. One she hits six, try to call for ganks from your jungler to blow her ult so that you can combo/kill her with ease. You may want to take AP marks for this matchup.

Zed

Very difficult lane, and almost impossible to win lane against a good Zed. Your best bet is to stay safe and CS with your Qs as much as possible. Take AP marks and exhaust instead of ghost for this matchup and RUSH ZHONYAS.

Fizz

Like Ahri, his kit makes it so that your ult is close to useless against him. Pre-six, harass him as much as possible; especially when you see him use his playful trickster ability. Consider getting Zhonyas for this matchup because if he lands your ult on you, you're basically calamari.

LeBlanc

By far the most difficult matchup for Vel'Koz. Try not to pick Vel'Koz if you see her picked. If you do, play extremely safe early game because she can definitely outdamage you. Don't feel like you can ever duel her because her W and her ult are way too stupid and therefore difficult for you to land any of your abilities on her. If you are a Vel'Koz one-trick, are placed mid, and see LeBlanc picked, just ask to play support.

Yasuo

LolCounter says Yasuo is the hardest counter for Vel'Koz, but I disagree. While Yasuo is, indeed, extremely mobile with his dashes, you can E when he gets to close to you. Once he's knocked-up, he can't use his windwall, allowing you to combo him. Best of all: his windwall DOES NOT block your ult. If you're too scared of him, then you can always CS with your abilities from far back. In team fights, avoid his tornado by staying at the backline of your team (duh) and poke as much as possible.

Annie

Easy matchup. Hit six first, land your Q on her, combo her, kill her. An Annie who falls behind early is pretty useless for a long time. Pre-six you can harass her easily because she's super immobile. If she does happen to hit six first, play safe until you hit six. If you don't feel confident enough, call your jungler over to blow either her ult or her flash. If either occurs, you can easily destroy her.

Lux

The main reason I love playing Vel'Koz. If she lands an ability on you and tries to auto-attack you to proc her passive, you can easily W-E or Q-W-E combo her, and she will never dare challenge you again. If you are both six and she lands her snare on you, W-E-Q-R combo her when she gets close and you'll kill her before she kills you. If you land a Q on her, combo her with W-E-R and she's dead.

Katarina

Avoid standing next to her knives and you should be all right. Don't expect to kill her in lane because her Shunpo has an extremely low cooldown with her Q, W, and her passive. If she ults, immediately place your E under her and she'll have to cancel her ult or risk dying to your combo. In teamfights you should be more useful than she is.

Aurelion Sol

His Q can cancel your ult but that's pretty much all he's got on you. Dodge his passive and once he uses his Q, blow him up. If he runs low on mana, then he'll have to auto-attack to CS, which means you can easily land your combo on him. If you land a Q on him, then you can also blow him up with your W-E combo.

Ekko

Really mobile and can survive your combo with his ult. Harass him as much as possible and look to combo him once you hit your Q. Try to hit six as quickly as possible so you can kill him while he doesn't have his ult. If you guys are both six, then call for the jungler to gank and blow his cooldowns and proceed to kill him on your own with the same combo.

Ezreal

Nothing he has can cancel your ult. Once he Es, try to land a Q on him and if it lands, proceed to W-E-(R) combo him. Be careful of his early game damage and you should easily win this lane.

Orianna

Stay away from her ball obviously and flash her ult if you have to. If she whiffs her ult, then you can easily crush her if you land a Q since she is pretty immobile.

Malzahar

Auto-attack to disable his spell-shield, and land your Q on him and W-E-R combo him. His minions can easily be destroyed while you CS with a quick and easy W-E-(W). He will never have the chance to ult you if you (Q)-W-E-R him since he'll still be knocked-up when he dies.

Syndra

People make this matchup seem so much harder than it really is. If she misses her stun, you have a ton of time to kill her with your own combo. Don't be afraid of her.

Kassadin

His Q can cancel your ult, but pre-6 try to ult harass him as much as possible and actually push in your lane. Kassadin sucks at CSing when the lane is pushed on him and also prevents him from roaming, which is one of his greatest strengths. Don't expect to kill him when you're both six. Try your best to match his roams. Even if he does get kills in his roams, you can arrive a few seconds later and clean up.

Karthus

Gangplank

Auto-attack his barrels when you can and try to land your Qs on him followed by a combo. This should be an extremely easy matchup.

Kog'Maw

Heimerdinger

Your waveclear destroys his turrets super easily, giving you free gold and making him almost completely useless. He's also extremely immobile, so you can easily combo him if you land your Q.

Diana

Her ult and her knockup make this matchup really tough. Call for help when you can, and try to harass her as much as possible before she hits 6; give her respect once she does by CSing from afar and dodging her Q.

Jayce

Avoid his Qs obvisouly and you should be fine.

Cassiopeia

Akali

Her ult is super annoying since she can just right behind you while you ult. If she hides in her W, you can still kill her because all your abilities don't require vision to trigger, so you can guess and kill her with W-E-Q-R.

Brand

If he walks up to use any of his combos on you, perform your combo and disintegrate the life out of him with Q-W-E-R. Avoid his W-Q stun and this matchup becomes one of Vel'Koz's easiest.

Lulu

Easy matchup. If she uses her whimsy ability, you can safely combo her and at least force her to burn her ult and/or flash. If she does either, ask for a gank and she's as good as dead.

Viktor

If you land a combo on him you can easily kill him since he'll be knocked-up before he can cancel your ult with his ult; your superior range should help with doing the aforementioned.

Twisted Fate

If he walks up to use any of cards on you, perform your combo and disintegrate the life out of him with Q-W-E-R.

Ryze

Stand away from your own minions and you should be safe from his harass. If he tries to go up to combo you, you can combo straight back, but don't waste your E to hastily. In this matchup, it's okay just to W-Q or Q-W him and run away.

Morgana

Taliyah

She's annoying because you can't really land your combo on her since she can CS from afar and she has superior roaming ability. Avoid her W knock-back and you will do fine against her. If you see the chance to kill her by landing your Q on her, then try to combo her. Don't be so afraid.

Anivia

Her kit is really frustrating, and it's just a matchup of who can land their skillshots more and at the right times.

Vladimir

Morellonomicon, which you typically rush, will make Vladimir almost useless. Like the matchup against Swain, you should be able to sear Vladimir.

Talon

Take exhaust for this matchup to reduce his burst and kill potential. He has superior roaming which you can try to match/cleanup. Respect his burst once he hits level 2 by CSing from afar. He will try to roam, so you MUST clear your lane of minions as soon as possible and try to match his roams.

Swain

Morellonomicon, which you typically rush, will make Swain's ultimate almost useless. You should be able to sear him.