1 Eliminate sugar (including fruit juices and sports drinks) and all flour
2 Start eating proper fats - Use healthy animal fats to substitute fat calories for carb calories. Drink whole cream or half and half instead of milk.
3 Eliminate grains
4 Eliminate grain and seed derived oils (cooking oils) Cook with butter, animal fats, or coconut oil.
5 Get daily midday sun or take 4-8000 iu vit D daily
6 Intermittent fasting and infrequent meals (2 meals a day is best)
7 Fruit is just a candy bar from a tree. Stick with berries and avoid watermelon which is pure fructose. Eat in moderation.
8 Eliminate legumes
9 Adjust your 6s and 3s. Pastured (grass fed) dairy and grass fed beef or bison avoids excess O-6 fatty acids and are better than supplementing with 0-3 supplements.
10 Proper exercise - emphasizing resistance and interval training over long aerobic sessions
11 Eliminate milk (if you are sensitive to it, move this up the list
12 Eliminate other dairy including cheese- (now you are "orthodox paleolithic")
I'm a geneticist, myself, so I tend to take a more customized view of issues like this. Paleonu's suggested steps are a fantastic place to start, but remember we're talking biology, not religion, and we all vary biologically to some extent. Personally, I put less emphasis on being orthodox and more on how my body responds.
This means that dairy, for me, is in, but not in huge amounts. Since some human lineages (mine included) evolved to preserve the ability to digest milk, it make sense that there's an advantage to it for those folks. It's going to vary. Most humans are NOT fully lactose tolerant, so they, for sure, should avoid milk.
Keep in mind that humans are omnivores and can do well on a huge variety of diets, so if your particular genetic makeup doesn't agree with something on the "good" list, don't eat it, and vice versa. Just be sure you're listening to how healthy you feel not to the addictive qualities some foods have (like sugar).
Just eliminating soy, wheat and corn from your diet is a one way to start.
Without them, you can't eat anything out of a box, and it really makes you think about what you're eating.
Get you head around the science, read Gary Taubes ...understand what becoming ketoadapted means ...be ready to have some slight headaches and withdrawal like symptoms ...drink water ...if you have weight to lose enjoy ketosis it'll probably only happen once its one great feeling of energy surfing ....have meals worked out in advance until it becomes natural to avoid carbes that take you over 50-100 grams a day .... find decent eggs, free range pork belly's , new zealand lamb, pastured beef, fish and offal ...don't overeat protein ...use fat for energy... , .... always have cream to hand and butter .... save good fat from cooking ...work out your green veg, and prepare great salads .... be prepared to virtually give up alcohol...other than in small measures....read the blogs.... listen to your body it will demand decent nutrition after a while ....be prepared for ridicule, but understand why the alternative is ridiculous ...only eat when your hungry... and be prepared to be rarely hungry .... enjoy the ability to intermittently fast and do weights .... have fun with it .... experiment ...adapt & evolve
I started a bit differently. I went paleo one meal at a time. I started with lunches and the 'Big Ass Salad' concept from MDA. After that I moved to snacks and then finally dinners. It allowed me to 'cheat' my way into the diet.
Read Mark Sisson's book, which is convincing. It's necessary to be convinced! Then start. Of course you will fail. But because you are convinced, you will not give up. It may take a few days, or if you are like me it make take many months, but you'll get there. At first you will fail in a multitude of ways every day, and the project will seem impossibly ambitious, but by taking two steps forward and one step back you will slowly get more and more consistent. Inevitably there will be days days of complete disaster, but over time it will become hours of complete disaster, then minutes. And one day, it'll be second nature.
"Then start," I said above. But where? I personally started with cutting out grains because that resonated with me, and because I couldn't face cutting back on sugar. At some point the grains became easy. So I was ready to give up sugar, but not artificial sweeteners. As I got more educated about artificial sweeteners, I sadly learned that I had to give them up too, but that's easy to do once you're educated enough to know how bad they are for you! I added the other pieces as the urge struck me.
You will doubtless do this differently, depending on your temperament. You may like to do things all at once. You might like to go piece-by-piece. You might have a sweet tooth like me and decide to tackle that later than you otherwise would. You might decide to keep in dairy, but then find cutting it out gives you better results. You might find that 85% cocoa chocolate is a great cheat at first, but then you start to binge on it so you need to cut it out. As long as you are convinced and persistent, start wherever you are moved to, and you'll do fine. Just keep experimenting, and never say die.
I started Paleo by eliminating all grains, dairy (except full fat cream and butter) and processed foods. i.e. pre-packaged foods made by man. I also eliminated almost all my extra sugars. I still put a teaspoon of sugar into my coffee and once a week I allow myself to have a "cheat meal" which sometimes (and sometimes doesn't involve sugar). It's really important to listen to your body and after a month of paleo, I was still having hunger and craving issues. I craved fat and sweets (in the form of high glycemic fruits mainly like bananas and raisins) Anyway, I have decided that I am rather carb sensitive and have since eliminated higher glycemic carbs like fruits from my diet in the morning and at lunch and replaced those calories with fats like avocado and nuts. By not eating these types of foods early in the day, I manage to completely avoid the cravings and eliminate the hunger.
IMO the quickest and easiest way to "start" eating paleo it to stick to foods that are in their "whole" or "true" form....in other words, not processed or "created" by man. Note these foods can be found at local farmers markets, abbatoirs, backyard gardens and orchards and the outside edges of your local grocer
Learn and memorize what foods are paleo and those which aren't:
By doing the following:
Does gut flora change due to diet? 7 Answers