Where do you find heracross?

Heracross are found most commonly around ecrutik by headbutting trees, but you can headbutt trees anywhere and they will appear, but they are rare, so prepare for a couple hours hard headbutting.

I found mine by Headbutting trees east of Ecruteak.

I realize this is like two months after the answer was posted, but it MIGHT help others who are looking at the question!

Heracross is easiest to get by headbutting the trees just above Slowpoke Well in Azalea Town. They're usually level 10, so you can raise them and they'll be a good part of your team, because they'll like you better.

Em, I hope that helped at all... - Kristen

You need to headbutt trees to get a heracross.
Hope this helps :D

East of Ecruteak there are trees you can use Headbutt on, and the results stand a chance of a Heracross.

What about time of day?

Bug Pokemon (and indeed, real bugs) come out in early morning. Go headbutt-hunting then.

Above answer is wrong.

Bug Pokemon do indeed come out in the morning, but they sleep at night. They sleep in trees. So headbutt them at night.

Y0u can find heracr0ss beetween?it's a secret hehe like this t0 kn0w the answer

I've been headbutting trees for hours (if you add up all the time I've spent trying to get heracross, over the past weeks..)
So I tried east of ecruteak and after about ten run-aways and many more failed headbuttings with NO bloody Pokemon, I gave up and tried the trees above slowpoke well
And amazing! After two sparrows and one aipom I got my heracross
FINALLY

Ive been searching for six hours and havent found it I've been to azela town and ecruteak going back to azela town in morning this time

Go above slowpoke well. Easy find

You can fin common pinsir and rare scyther in the bug catching contest

Azalea town above the slowpoke well. After hours half an hour at Ecruteak, I got it at Azalea in about 2 hits.

Found on Route 44 5 trees away from the second person you see(fat guy) exiting Ecruteak after 8:30pm. It contained sleeping Sparrows and wake Aipoms.

1: This is called the "Hera Tree". Heracross can only spawn from a tree with this quality.

2: The Hera Tree is always "high-rate"; meaning that it has a quality ensuring that you will very likely encounter a Pokemon each time you headbutt the tree(over 50%).

3: He will always be obtainable from this tree; the tree will not lose this property from resetting or leaving and reentering the area.

4: (Speculation)The tree is created the moment you start a new game, and will not always be in the same place.

My favourite place for catching heracross is in azalea town behind Kurt' s house, the first tree from the right. 6 tries - 2 heracrosses.(Monday 8.40 am)

However in my other crystal version, editated I cannot find him - editet shops and Pokemon in grass, but not trees, so I think it' s about it. Only spearow, aipom and sometimes ekans appears.

Azalea Town. That is the easiest place to get it. Got it in 2 minutes.

Azela town near slowpoke cave I got 6 heracross in a row during night

Yes!! Whoever said slowpoke well is a weird place DIE! I just caught a SHINY HERACROSS THEREqq

There is this new Pokemon in Crystal called Skarmory and it's rare! He is at route 45 and it will take a while and he is Steel Flying type

For me, it was left-most tree above the Slowpoke Well, I got 3 Heracross in 8 tries

On bulbapedia it lists a sepertate Pokemon spawn as 'special tree' with mostly the same polemon as any tree, and heracross. What makes a tree special, whixh ones they are or when they get set is not elaborated apon. My guess is it's to make you headbutt all the trees, and not just break one of your pokemon's faces headbutting one treeover and over again.

After searching several locations, best spot was found behind the well. Headbutt the tree furthest to the right behind the well. This tree in the corner gave encounters with every hit, dropping Spear ow, Aipom, and the big H. No Ekans. This can be done at night, when I did it.

I was reading the wiki and it said that the chance to find a low or moderate encounter of a tree depends on the last digit of your player id, (Mine is 1, and I am having no luck at all.) and there is a formula depending on the location of the tree. The formula might be a little messed up though. It says the moderate encounter rate trees are supposed to have ekans, and the low encounter rate trees have heracross instead of ekans. I am trying in azalea town, and all the trees that I have tried have had ekans. Any help?
P.S. It might be because I am playing Pokemon vietnamese crystal and it is sort of broken and it wouldn't let me get the odd egg.

I feel a bit silly replying to such an old post but gosh darnit I think I found the magical tree! Now this could just be a glitch with my game so hopefully someone will see this and verify.
Anywas, out of 15 headbutts (not battles) of this tree I got 6 Heracross (yup 6) and even got 3 b2b. Less important but still interesting is that every headbutt dropped a pokémon and I probably hit it like 40 times before starting a count. Now heres what you've been waiting for: The location. Head east out of Mahogany Town onto Route 44. There is a berry tree north of the first trainer. Head up to it and go east of it until you see two little trees by themselves. The southernmost tree is the one you want.
Day is Monday, time 1:30am (I'll check if this matters)
To the one person this saves hours of searching, you're welcome.