Version control comes first
A commentator on my last entry wrote (in part):
I also find that sometimes [version control] can fall short in providing context to a change. Good living documentation (wiki, OneNote, etc.) makes up for the area that strict version control cannot; providing the reader with some understanding on context, and "why."
It is my position that most organization can benefit most from a good wiki (or something to that affect), then introduce opportunities for file based version control at a later date.
I very much disagree with this view for both general and pragmatic reasons.
Wikis create (theoretically) living documentation. Documentation is nice, but it is not crucial. (Ask lots of people.)
Version control creates much safer changes (you can see exactly what you changed and you can see how things used to be back when they worked (and you can go back to them)). It is an unusual environment that is not making changes frequently (sysadmins generally exist in large part to make changes) but changes are dangerous. Making changes safer is crucial and a major improvement in your environment.
That is the general reason. Now to the pragmatic one.
At this point in time, any place that's lacking both living documentation and version control is in a bad situation. Either they're so culturally backwards that they haven't been convinced of the virtues of either or they are so badly managed that their sysadmins can't create either. In a place that's backwards, dysfunctional, or both, simple version control is going to be much easier to introduce than living documentation, partly because it's much easier than writing documentation and partly because it can start paying off almost immediately.
Simple version control has a major additional benefit in an organization with problems: it fails much safer. If people stop using simple version control, nothing particularly bad happens (you revert to the status quo ante where you had no change tracking). If people stop updating your living documentation, what you have is misleading, out of date documentation; like incorrect comments in code, this is worse and more dangerous than having no documentation at all.
(This applies in the small as well as in the large, where you don't do a checkin or don't do a documentation update. It's also much easier to catch a missed checkin than a missed documentation update.)