The cross-linked (1 x 2) reconstruction of TiO2(110) is a frequently observed phase reflecting the surface structure of titania in a significantly reduced state. Here we resolve the atomic scale structure of the cross-linked (1 x 2) phase with dynamic scanning force microscopy operated in the non-contact mode (NC-AFM). From an analysis of the atomic-scale contrast patterns of the titanium and oxygen sub-structures obtained by imaging the surface with AFM tips having different tip apex termination, we infer the hitherto most accurate model of the atomic structure of the cross-linked (1 x 2) phase. Our findings suggest that the reconstruction is based on added rows in [001] direction built up of Ti3O6 units with an uninterrupted central string of oxygen atoms accompanied by a regular sequence of cross-links consisting of linear triples of additional oxygen atoms in between the rows. The new insight obtained from NC-AFM solves previous controversy about the cross-linked TiO2(110) surface structure, since previously proposed models based on cross-links with a lower O content do not appear to be consistent with the atom-resolved data presented here. Instead, our measurements strongly support the Ti3O6 motif to be the structural base of the cross-linked (1 x 2) reconstruction of TiO2(110).