HI Dan, good luck with your goals! Yes, it is possible to gain muscle on a paleo diet. I put on 20# of muscle over the last couple years (i'm female). I'm sure being a male you would be able to put more on. Several guys on this list are weight lifters. For protein sources, well, any dead animals is good... I make a smoothie every morning with egg white powder, coconut milk, fruit. (I was able to get my small local health food store to sell me 10 pounds of powdered egg whites for $82 u.s. dollars. I think it tastes better than any whey, though I must admit I never found one that tasted good! Egg white powder is pretty tasteless) I eat meat/protein at each meal, veggies at a few meals, and about 2-4 servings of fruit a day. Good luck and keep us posted on your progress. --Liz