I wasn't a vegetarian for that long, just about 2 years, was pescetarian before that. I started eating meat before going primal though since I just seriously lacked energy on a vegetarian diet, though I was apparently getting my RDA for everything.
What are you eating every day? I think it's a good idea to work your way up to things. I went to chicken first, then pork, then beef, etc. It would probably be best experiencing it as a composed dish (a soup or stew) instead of straight-up steak (which I didn't appreciate until later). Remember that humans were meant to be omnivores.
And keep the quality of meats as high as you can...organic/grassfed/free-range, etc.