The structural changes upon cation substitution in natural AB2O6 columbites have been studied by means of single-crystal X-ray diffraction. Most of the structural variations across the MnNb2O6-FeNb2O6 solid solution in completely ordered samples can be simply understood in terms of ionic radii. The substitution of Fe for the larger Mn cation causes a linear decrease of all unit-cell parameters. Going from manganocolumbite to ferrocolumbite the site A is reduced in volume and becomes less distorted. The oxygen cage around the cation assumes a more regular arrangement since the mismatch between A and B chains decreases. At the same time, the divalent cation moves toward the barycenter of the polyhedron. The B site, which is not involved in the Fe-Mn cation substitution, maintains its geometry unchanged. Ordering of divalent cations at A sites and pentavalent cations at B sites causes linear variations of a and c cell parameters. A non-linear behavior is shown by the b cell parameter that shows a minimum at order parameter Qm ~ 0.7. A discontinuity at this Qm value is also shown by other structural parameters. Cation ordering also causes volume variations of the two octahedral sites as a consequence of the different ionic radii of the various species. Octahedral bond-length distortion parameters show that the B site is in general more distorted than the A site; distortion of the B site increases with ordering due to higher cation-cation repulsion along the B octahedral chain and to the second-order Jahn-Teller (SOJT) effect. Octahedral chains respond to modifications of the polyhedra by folding along the common edge.