Currently I have been working on my boss man's old barn. It has three stables, hay room, loft, and storage. He bought a house that was built in 1860 and it has the barn on the property. The barn was relocated there on that property 100 yrs ago (or close). So the actual age of the barn is unknown. It has timbers in it that are 16"x16"x16"x16"... LOL It was in a town that is 30 or so miles from where it is sitting now. How they moved such a beast back then I have no idea. There is some areas of beams that are petrified. Also a fellow couldn't get past the war he was in WWI (I believe thats what they said) and he hung himself in that barn. Creepy...
My job is to rip off the old siding and replace it with rough cut siding form a saw mill. My boss still wants the old look but also have better weather protect that what it had. One thing that has been a killer is the barn was not plumbed back up so it is out of square. This is a nightmare trying to put siding up and it look like it should. I have had to fir out the corners to make it look good. Long story. If you do get it moved just make sure you have it squared up and plumb in each corner. This can be done with temporary bracing until you start putting the siding back on or whatever you are going to use to cover it. So it would be best to install the bracing on the inside of the barn. Therefore it won't be in the way once the siding goes up. I've also built a loft door, and two sliding doors for the barn.
Of course since you're starting afresh I would recommend a footing being dug, rebar installed, and concrete. Have the barn located over the footings (still setting on house moving equipment) then let the block mason come in. The house moving guy will take it from there because he more than likely has done this a time or two.
Just make sure it's level, square, and plumb!! Makes things easier on the old carpenter! LOL